Ii-2019

• Paper 4, Section II, F

  Algebraic Geometry

  Part II, 2019

  (a) Let $X \subseteq \mathbb{P}^{2}$ be a smooth projective plane curve, defined by a homogeneous polynomial $F(x, y, z)$ of degree $d$ over the complex numbers $\mathbb{C}$.

  (i) Define the divisor $[X \cap H]$, where $H$ is a hyperplane in $\mathbb{P}^{2}$ not contained in $X$, and prove that it has degree $d$.

  (ii) Give (without proof) an expression for the degree of $\mathcal{K}_{X}$ in terms of $d$.

  (iii) Show that $X$ does not have genus 2 .

  (b) Let $X$ be a smooth projective curve of genus $g$ over the complex numbers $\mathbb{C}$. For $p \in X$ let

  $G(p)=\left\{n \in \mathbb{N} \mid\right.$ there is no $f \in k(X)$ with $v_{p}(f)=n$, and $v_{q}(f) \leqslant 0$ for all $\left.q \neq p\right\} .$

  (i) Define $\ell(D)$, for a divisor $D$.

  (ii) Show that for all $p \in X$,

  $$\ell(n p)= \begin{cases}\ell((n-1) p) & \text { for } n \in G(p) \\ \ell((n-1) p)+1 & \text { otherwise }\end{cases}$$

  (iii) Show that $G(p)$ has exactly $g$ elements. [Hint: What happens for large $n$ ?]

  (iv) Now suppose that $X$ has genus 2 . Show that $G(p)=\{1,2\}$ or $G(p)=\{1,3\}$.

  [In this question $\mathbb{N}$ denotes the set of positive integers.]

  comment

• Paper 3, Section II, F

  Algebraic Geometry

  Part II, 2019

  Let $W \subseteq \mathbb{A}^{2}$ be the curve defined by the equation $y^{3}=x^{4}+1$ over the complex numbers $\mathbb{C}$, and let $X \subseteq \mathbb{P}^{2}$ be its closure.

  (a) Show $X$ is smooth.

  (b) Determine the ramification points of the $\operatorname{map} X \rightarrow \mathbb{P}^{1}$ defined by

  $$(x: y: z) \mapsto(x: z) .$$

  Using this, determine the Euler characteristic and genus of $X$, stating clearly any theorems that you are using.

  (c) Let $\omega=\frac{d x}{y^{2}} \in \mathcal{K}_{X}$. Compute $\nu_{p}(\omega)$ for all $p \in X$, and determine a basis for $\mathcal{L}\left(\mathcal{K}_{X}\right)$

  comment

• Paper 2, Section II, F

  Algebraic Geometry

  Part II, 2019

  (a) Let $A$ be a commutative algebra over a field $k$, and $p: A \rightarrow k$ a $k$-linear homomorphism. Define $\operatorname{Der}(A, p)$, the derivations of $A$ centered in $p$, and define the tangent space $T_{p} A$ in terms of this.

  Show directly from your definition that if $f \in A$ is not a zero divisor and $p(f) \neq 0$, then the natural map $T_{p} A\left[\frac{1}{f}\right] \rightarrow T_{p} A$ is an isomorphism.

  (b) Suppose $k$ is an algebraically closed field and $\lambda_{i} \in k$ for $1 \leqslant i \leqslant r$. Let

  $$X=\left\{(x, y) \in \mathbb{A}^{2} \mid x \neq 0, y \neq 0, y^{2}=\left(x-\lambda_{1}\right) \cdots\left(x-\lambda_{r}\right)\right\}$$

  Find a surjective map $X \rightarrow \mathbb{A}^{1}$. Justify your answer.

  comment

• Paper 1, Section II, F

  Algebraic Geometry

  Part II, 2019

  (a) Let $k$ be an algebraically closed field of characteristic 0 . Consider the algebraic variety $V \subset \mathbb{A}^{3}$ defined over $k$ by the polynomials

  $$x y, \quad y^{2}-z^{3}+x z, \quad \text { and } x(x+y+2 z+1)$$

  Determine

  (i) the irreducible components of $V$,

  (ii) the tangent space at each point of $V$,

  (iii) for each irreducible component, the smooth points of that component, and

  (iv) the dimensions of the irreducible components.

  (b) Let $L \supseteq K$ be a finite extension of fields, and $\operatorname{dim}_{K} L=n$. Identify $L$ with $\mathbb{A}^{n}$ over $K$ and show that

  $$U=\{\alpha \in L \mid K[\alpha]=L\}$$

  is the complement in $\mathbb{A}^{n}$ of the vanishing set of some polynomial. [You need not show that $U$ is non-empty. You may assume that $K[\alpha]=L$ if and only if $1, \alpha, \ldots, \alpha^{n-1}$ form a basis of $L$ over $K$.]

  comment

• Paper 3, Section II, F

  Algebraic Topology

  Part II, 2019

  Let $K$ be a simplicial complex, and $L$ a subcomplex. As usual, $C_{k}(K)$ denotes the group of $k$-chains of $K$, and $C_{k}(L)$ denotes the group of $k$-chains of $L$.

  (a) Let

  $$C_{k}(K, L)=C_{k}(K) / C_{k}(L)$$

  for each integer $k$. Prove that the boundary map of $K$ descends to give $C_{\bullet}(K, L)$ the structure of a chain complex.

  (b) The homology groups of $K$ relative to $L$, denoted by $H_{k}(K, L)$, are defined to be the homology groups of the chain complex $C_{\bullet}(K, L)$. Prove that there is a long exact sequence that relates the homology groups of $K$ relative to $L$ to the homology groups of $K$ and the homology groups of $L$.

  (c) Let $D_{n}$ be the closed $n$-dimensional disc, and $S^{n-1}$ be the $(n-1)$-dimensional sphere. Exhibit simplicial complexes $K_{n}$ and subcomplexes $L_{n-1}$ such that $D_{n} \cong\left|K_{n}\right|$ in such a way that $\left|L_{n-1}\right|$ is identified with $S^{n-1}$.

  (d) Compute the relative homology groups $H_{k}\left(K_{n}, L_{n-1}\right)$, for all integers $k \geqslant 0$ and $n \geqslant 2$ where $K_{n}$ and $L_{n-1}$ are as in (c).

  comment

• Paper 4, Section II, F

  Algebraic Topology

  Part II, 2019

  State the Lefschetz fixed point theorem.

  Let $n \geqslant 2$ be an integer, and $x_{0} \in S^{2}$ a choice of base point. Define a space

  $$X:=\left(S^{2} \times \mathbb{Z} / n \mathbb{Z}\right) / \sim$$

  where $\mathbb{Z} / n \mathbb{Z}$ is discrete and $\sim$ is the smallest equivalence relation such that $\left(x_{0}, i\right) \sim$ $\left(-x_{0}, i+1\right)$ for all $i \in \mathbb{Z} / n \mathbb{Z}$. Let $\phi: X \rightarrow X$ be a homeomorphism without fixed points. Use the Lefschetz fixed point theorem to prove the following facts.

  (i) If $\phi^{3}=\mathrm{Id}_{X}$ then $n$ is divisible by 3 .

  (ii) If $\phi^{2}=\operatorname{Id}_{X}$ then $n$ is even.

  comment

• Paper 2, Section II, F

  Algebraic Topology

  Part II, 2019

  Let $T=S^{1} \times S^{1}, U=S^{1} \times D^{2}$ and $V=D^{2} \times S^{1}$. Let $i: T \rightarrow U, j: T \rightarrow V$ be the natural inclusion maps. Consider the space $S:=U \cup_{T} V$; that is,

  $$S:=(U \sqcup V) / \sim$$

  where $\sim$ is the smallest equivalence relation such that $i(x) \sim j(x)$ for all $x \in T$.

  (a) Prove that $S$ is homeomorphic to the 3 -sphere $S^{3}$.

  [Hint: It may help to think of $S^{3}$ as contained in $\mathbb{C}^{2}$.]

  (b) Identify $T$ as a quotient of the square $I \times I$ in the usual way. Let $K$ be the circle in $T$ given by the equation $y=\frac{2}{3} x \bmod 1 . K$ is illustrated in the figure below.

  

  Compute a presentation for $\pi_{1}(S-K)$, where $S-K$ is the complement of $K$ in $S$, and deduce that $\pi_{1}(S-K)$ is non-abelian.

  comment

• Paper 1, Section II, F

  Algebraic Topology

  Part II, 2019

  In this question, $X$ and $Y$ are path-connected, locally simply connected spaces.

  (a) Let $f: Y \rightarrow X$ be a continuous map, and $\widehat{X}$ a path-connected covering space of $X$. State and prove a uniqueness statement for lifts of $f$ to $\widehat{X}$.

  (b) Let $p: \widehat{X} \rightarrow X$ be a covering map. A covering transformation of $p$ is a homeomorphism $\phi: \widehat{X} \rightarrow \widehat{X}$ such that $p \circ \phi=p$. For each integer $n \geqslant 3$, give an example of a space $X$ and an $n$-sheeted covering map $p_{n}: \widehat{X}_{n} \rightarrow X$ such that the only covering transformation of $p_{n}$ is the identity map. Justify your answer. [Hint: Take $X$ to be a wedge of two circles.]

  (c) Is there a space $X$ and a 2-sheeted covering map $p_{2}: \widehat{X}_{2} \rightarrow X$ for which the only covering transformation of $p_{2}$ is the identity? Justify your answer briefly.

  comment

• Paper 3, Section II, H

  Analysis of Functions

  Part II, 2019

  (a) Prove that in a finite-dimensional normed vector space the weak and strong topologies coincide.

  (b) Prove that in a normed vector space $X$, a weakly convergent sequence is bounded. [Any form of the Banach-Steinhaus theorem may be used, as long as you state it clearly.]

  (c) Let $\ell^{1}$ be the space of real-valued absolutely summable sequences. Suppose $\left(a^{k}\right)$ is a weakly convergent sequence in $\ell^{1}$ which does not converge strongly. Show there is a constant $\varepsilon>0$ and a sequence $\left(x^{k}\right)$ in $\ell^{1}$ which satisfies $x^{k} \rightarrow 0$ and $\left\|x^{k}\right\|_{\ell^{1}} \geqslant \varepsilon$ for all $k \geqslant 1$.

  With $\left(x^{k}\right)$ as above, show there is some $y \in \ell^{\infty}$ and a subsequence $\left(x^{k_{n}}\right)$ of $\left(x^{k}\right)$ with $\left\langle x^{k_{n}}, y\right\rangle \geqslant \varepsilon / 3$ for all $n$. Deduce that every weakly convergent sequence in $\ell^{1}$ is strongly convergent.

  [Hint: Define $y$ so that $y_{i}=\operatorname{sign} x_{i}^{k_{n}}$ for $b_{n-1}<i \leqslant b_{n}$, where the sequence of integers $b_{n}$ should be defined inductively along with $\left.x^{k_{n}} .\right]$

  (d) Is the conclusion of part (c) still true if we replace $\ell^{1}$ by $L^{1}([0,2 \pi]) ?$

  comment

• Paper 1, Section II, H

  Analysis of Functions

  Part II, 2019

  (a) Consider the topology $\mathcal{T}$ on the natural numbers $\mathbb{N} \subset \mathbb{R}$ induced by the standard topology on $\mathbb{R}$. Prove it is the discrete topology; i.e. $\mathcal{T}=\mathcal{P}(\mathbb{N})$ is the power set of $\mathbb{N}$.

  (b) Describe the corresponding Borel sets on $\mathbb{N}$ and prove that any function $f: \mathbb{N} \rightarrow \mathbb{R}$ or $f: \mathbb{N} \rightarrow[0,+\infty]$ is measurable.

  (c) Using Lebesgue integration theory, define $\sum_{n \geqslant 1} f(n) \in[0,+\infty]$ for a function $f: \mathbb{N} \rightarrow[0,+\infty]$ and then $\sum_{n \geqslant 1} f(n) \in \mathbb{C}$ for $f: \mathbb{N} \rightarrow \mathbb{C}$. State any condition needed for the sum of the latter series to be defined. What is a simple function in this setting, and which simple functions have finite sum?

  (d) State and prove the Beppo Levi theorem (also known as the monotone convergence theorem).

  (e) Consider $f: \mathbb{R} \times \mathbb{N} \rightarrow[0,+\infty]$ such that for any $n \in \mathbb{N}$, the function $t \mapsto f(t, n)$ is non-decreasing. Prove that

  $$\lim _{t \rightarrow \infty} \sum_{n \geqslant 1} f(t, n)=\sum_{n \geqslant 1} \lim _{t \rightarrow \infty} f(t, n) .$$

  Show that this need not be the case if we drop the hypothesis that $t \mapsto f(t, n)$ is nondecreasing, even if all the relevant limits exist.

  comment

• Paper 4, Section II, B

  Applications of Quantum Mechanics

  Part II, 2019

  (a) A classical beam of particles scatters off a spherically symmetric potential $V(r)$. Draw a diagram to illustrate the differential cross-section $d \sigma / d \Omega$, and use this to derive an expression for $d \sigma / d \Omega$ in terms of the impact parameter $b$ and the scattering angle $\theta$.

  A quantum beam of particles of mass $m$ and momentum $p=\hbar k$ is incident along the $z$-axis and scatters off a spherically symmetric potential $V(r)$. Write down the asymptotic form of the wavefunction $\psi$ in terms of the scattering amplitude $f(\theta)$. By considering the probability current $\mathbf{J}=-i(\hbar / 2 m)\left(\psi^{\star} \nabla \psi-\left(\nabla \psi^{\star}\right) \psi\right)$, derive an expression for the differential cross-section $d \sigma / d \Omega$ in terms of $f(\theta)$.

  (b) The solution $\psi(\mathbf{r})$ of the radial Schrödinger equation for a particle of mass $m$ and wave number $k$ moving in a spherically symmetric potential $V(r)$ has the asymptotic form

  $$\psi(\mathbf{r}) \sim \sum_{l=0}^{\infty}\left[A_{l}(k) \frac{\sin \left(k r-\frac{l \pi}{2}\right)}{k r}-B_{l}(k) \frac{\cos \left(k r-\frac{l \pi}{2}\right)}{k r}\right] P_{l}(\cos \theta)$$

  valid for $k r \gg 1$, where $A_{l}(k)$ and $B_{l}(k)$ are constants and $P_{l}$ denotes the $l$ th Legendre polynomial. Define the S-matrix element $S_{l}$ and the corresponding phase shift $\delta_{l}$ for the partial wave of angular momentum $l$, in terms of $A_{l}(k)$ and $B_{l}(k)$. Define also the scattering length $a_{s}$ for the potential $V$.

  Outside some core region, $r>r_{0}$, the Schrödinger equation for some such potential is solved by the s-wave (i.e. $l=0$ ) wavefunction $\psi(\mathbf{r})=\psi(r)$ with,

  $$\psi(r)=\frac{e^{-i k r}}{r}+\frac{k+i \lambda \tanh (\lambda r)}{k-i \lambda} \frac{e^{i k r}}{r}$$

  where $\lambda>0$ is a constant. Extract the S-matrix element $S_{0}$, the phase shift $\delta_{0}$ and the scattering length $a_{s}$. Deduce that the potential $V(r)$ has a bound state of zero angular momentum and compute its energy. Give the form of the (un-normalised) bound state wavefunction in the region $r>r_{0}$.

  comment

• Paper 3, Section II, B

  Applications of Quantum Mechanics

  Part II, 2019

  A Hamiltonian $H$ is invariant under the discrete translational symmetry of a Bravais lattice $\Lambda$. This means that there exists a unitary translation operator $T_{\mathbf{r}}$ such that $\left[H, T_{\mathbf{r}}\right]=0$ for all $\mathbf{r} \in \Lambda$. State and prove Bloch's theorem for $H$.

  Consider the two-dimensional Bravais lattice $\Lambda$ defined by the basis vectors

  $$\mathbf{a}_{1}=\frac{a}{2}(\sqrt{3}, 1), \quad \mathbf{a}_{2}=\frac{a}{2}(\sqrt{3},-1)$$

  Find basis vectors $\mathbf{b}_{1}$ and $\mathbf{b}_{2}$ for the reciprocal lattice. Sketch the Brillouin zone. Explain why the Brillouin zone has only two physically distinct corners. Show that the positions of these corners may be taken to be $\mathbf{K}=\frac{1}{3}\left(2 \mathbf{b}_{1}+\mathbf{b}_{2}\right)$ and $\mathbf{K}^{\prime}=\frac{1}{3}\left(\mathbf{b}_{1}+2 \mathbf{b}_{2}\right)$.

  The dynamics of a single electron moving on the lattice $\Lambda$ is described by a tightbinding model with Hamiltonian

  $$H=\sum_{\mathbf{r} \in \Lambda}\left[E_{0}|\mathbf{r}\rangle\langle\mathbf{r}|-\lambda\left(|\mathbf{r}\rangle\left\langle\mathbf{r}+\mathbf{a}_{1}|+| \mathbf{r}\right\rangle\left\langle\mathbf{r}+\mathbf{a}_{2}|+| \mathbf{r}+\mathbf{a}_{1}\right\rangle\left\langle\mathbf{r}|+| \mathbf{r}+\mathbf{a}_{2}\right\rangle\langle\mathbf{r}|\right)\right]$$

  where $E_{0}$ and $\lambda$ are real parameters. What is the energy spectrum as a function of the wave vector $\mathbf{k}$ in the Brillouin zone? How does the energy vary along the boundary of the Brillouin zone between $\mathbf{K}$ and $\mathbf{K}^{\prime}$ ? What is the width of the band?

  In a real material, each site of the lattice $\Lambda$ contains an atom with a certain valency. Explain how the conducting properties of the material depend on the valency.

  Suppose now that there is a second band, with minimum $E=E_{0}+\Delta$. For what values of $\Delta$ and the valency is the material an insulator?

  comment

• Paper 4, Section II, H

  Analysis of Functions

  Part II, 2019

  (a) Let $(\mathcal{H},\langle\cdot, \cdot\rangle)$ be a real Hilbert space and let $B: \mathcal{H} \times \mathcal{H} \rightarrow \mathbb{R}$ be a bilinear map. If $B$ is continuous prove that there is an $M>0$ such that $|B(u, v)| \leqslant M\|u\|\|v\|$ for all $u, v \in \mathcal{H}$. [You may use any form of the Banach-Steinhaus theorem as long as you state it clearly.]

  (b) Now suppose that $B$ defined as above is bilinear and continuous, and assume also that it is coercive: i.e. there is a $C>0$ such that $B(u, u) \geqslant C\|u\|^{2}$ for all $u \in \mathcal{H}$. Prove that for any $f \in \mathcal{H}$, there exists a unique $v_{f} \in \mathcal{H}$ such that $B\left(u, v_{f}\right)=\langle u, f\rangle$ for all $u \in \mathcal{H}$.

  [Hint: show that there is a bounded invertible linear operator $L$ with bounded inverse so that $B(u, v)=\langle u, L v\rangle$ for all $u, v \in \mathcal{H}$. You may use any form of the Riesz representation theorem as long as you state it clearly.]

  (c) Define the Sobolev space $H_{0}^{1}(\Omega)$, where $\Omega \subset \mathbb{R}^{d}$ is open and bounded.

  (d) Suppose $f \in L^{2}(\Omega)$ and $A \in \mathbb{R}^{d}$ with $|A|_{2}<2$, where $|\cdot|_{2}$ is the Euclidean norm on $\mathbb{R}^{d}$. Consider the Dirichlet problem

  $$-\Delta v+v+A \cdot \nabla v=f \quad \text { in } \Omega, \quad v=0 \quad \text { in } \partial \Omega$$

  Using the result of part (b), prove there is a unique weak solution $v \in H_{0}^{1}(\Omega)$.

  (e) Now assume that $\Omega$ is the open unit disk in $\mathbb{R}^{2}$ and $g$ is a smooth function on $\mathbb{S}^{1}$. Sketch how you would solve the following variant:

  $$-\Delta v+v+A \cdot \nabla v=0 \quad \text { in } \Omega, \quad v=g \quad \text { in } \partial \Omega .$$

  [Hint: Reduce to the result of part (d).]

  comment

• Paper 2, Section II, B

  Applications of Quantum Mechanics

  Part II, 2019

  Give an account of the variational principle for establishing an upper bound on the ground state energy of a Hamiltonian $H$.

  A particle of mass $m$ moves in one dimension and experiences the potential $V=A|x|^{n}$ with $n$ an integer. Use a variational argument to prove the virial theorem,

  $$2\langle T\rangle_{0}=n\langle V\rangle_{0}$$

  where $\langle\cdot\rangle_{0}$ denotes the expectation value in the true ground state. Deduce that there is no normalisable ground state for $n \leqslant-3$.

  For the case $n=1$, use the ansatz $\psi(x) \propto e^{-\alpha^{2} x^{2}}$ to find an estimate for the energy of the ground state.

  comment

• Paper 1, Section II, B

  Applications of Quantum Mechanics

  Part II, 2019

  A particle of mass $m$ and charge $q$ moving in a uniform magnetic field $\mathbf{B}=\nabla \times \mathbf{A}=$ $(0,0, B)$ and electric field $\mathbf{E}=-\nabla \phi$ is described by the Hamiltonian

  $$H=\frac{1}{2 m}|\mathbf{p}-q \mathbf{A}|^{2}+q \phi$$

  where $\mathbf{p}$ is the canonical momentum.

  [ In the following you may use without proof any results concerning the spectrum of the harmonic oscillator as long as they are stated clearly.]

  (a) Let $\mathbf{E}=\mathbf{0}$. Choose a gauge which preserves translational symmetry in the $y$ direction. Determine the spectrum of the system, restricted to states with $p_{z}=0$. The system is further restricted to lie in a rectangle of area $A=L_{x} L_{y}$, with sides of length $L_{x}$ and $L_{y}$ parallel to the $x$ - and $y$-axes respectively. Assuming periodic boundary conditions in the $y$-direction, estimate the degeneracy of each Landau level.

  (b) Consider the introduction of an additional electric field $\mathbf{E}=(\mathcal{E}, 0,0)$. Choosing a suitable gauge (with the same choice of vector potential $\mathbf{A}$ as in part (a)), write down the resulting Hamiltonian. Find the energy spectrum for a particle on $\mathbb{R}^{3}$ again restricted to states with $p_{z}=0$.

  Define the group velocity of the electron and show that its $y$-component is given by $v_{y}=-\mathcal{E} / B$.

  When the system is further restricted to a rectangle of area $A$ as above, show that the previous degeneracy of the Landau levels is lifted and determine the resulting energy gap $\Delta E$ between the ground-state and the first excited state.

  comment

• Paper 4, Section II, K

  Applied Probability

  Part II, 2019

  (a) Let $\lambda: \mathbb{R}^{d} \rightarrow[0, \infty)$ be such that $\Lambda(A):=\int_{A} \lambda(\mathbf{x}) d \mathbf{x}$ is finite for any bounded measurable set $A \subseteq \mathbb{R}^{d}$. State the properties which define a (non-homogeneous) Poisson process $\Pi$ on $\mathbb{R}^{d}$ with intensity function $\lambda$.

  (b) Let $\Pi$ be a Poisson process on $\mathbb{R}^{d}$ with intensity function $\lambda$, and let $f: \mathbb{R}^{d} \rightarrow \mathbb{R}^{s}$ be a given function. Give a clear statement of the necessary conditions on the pair $\Lambda, f$ subject to which $f(\Pi)$ is a Poisson process on $\mathbb{R}^{s}$. When these conditions hold, express the mean measure of $f(\Pi)$ in terms of $\Lambda$ and $f$.

  (c) Let $\Pi$ be a homogeneous Poisson process on $\mathbb{R}^{2}$ with constant intensity 1 , and let $f: \mathbb{R}^{2} \rightarrow[0, \infty)$ be given by $f\left(x_{1}, x_{2}\right)=x_{1}^{2}+x_{2}^{2}$. Show that $f(\Pi)$ is a homogeneous Poisson process on $[0, \infty)$ with constant intensity $\pi$.

  Let $R_{1}, R_{2}, \ldots$ be an increasing sequence of positive random variables such that the points of $f(\Pi)$ are $R_{1}^{2}, R_{2}^{2}, \ldots$ Show that $R_{k}$ has density function

  $$h_{k}(r)=\frac{1}{(k-1) !} 2 \pi r\left(\pi r^{2}\right)^{k-1} e^{-\pi r^{2}}, \quad r>0$$

  comment

• Paper 3, Section II, K

  Applied Probability

  Part II, 2019

  (a) What does it mean to say that a continuous-time Markov chain $X=\left(X_{t}: 0 \leqslant\right.$ $t \leqslant T$ ) with state space $S$ is reversible in equilibrium? State the detailed balance equations, and show that any probability distribution on $S$ satisfying them is invariant for the chain.

  (b) Customers arrive in a shop in the manner of a Poisson process with rate $\lambda>0$. There are $s$ servers, and capacity for up to $N$ people waiting for service. Any customer arriving when the shop is full (in that the total number of customers present is $N+s$ ) is not admitted and never returns. Service times are exponentially distributed with parameter $\mu>0$, and they are independent of one another and of the arrivals process. Describe the number $X_{t}$ of customers in the shop at time $t$ as a Markov chain.

  Calculate the invariant distribution $\pi$ of $X=\left(X_{t}: t \geqslant 0\right)$, and explain why $\pi$ is the unique invariant distribution. Show that $X$ is reversible in equilibrium.

  [Any general result from the course may be used without proof, but must be stated clearly.]

  comment

• Paper 2, Section II, K

  Applied Probability

  Part II, 2019

  Let $X=\left(X_{t}: t \geqslant 0\right)$ be a Markov chain on the non-negative integers with generator $G=\left(g_{i, j}\right)$ given by

  $$\begin{aligned} g_{i, i+1} &=\lambda_{i}, & & i \geqslant 0 \\ g_{i, 0} &=\lambda_{i} \rho_{i}, & & i>0 \\ g_{i, j} &=0, & & j \neq 0, i, i+1 \end{aligned}$$

  for a given collection of positive numbers $\lambda_{i}, \rho_{i}$.

  (a) State the transition matrix of the jump chain $Y$ of $X$.

  (b) Why is $X$ not reversible?

  (c) Prove that $X$ is transient if and only if $\prod_{i}\left(1+\rho_{i}\right)<\infty$.

  (d) Assume that $\prod_{i}\left(1+\rho_{i}\right)<\infty$. Derive a necessary and sufficient condition on the parameters $\lambda_{i}, \rho_{i}$ for $X$ to be explosive.

  (e) Derive a necessary and sufficient condition on the parameters $\lambda_{i}, \rho_{i}$ for the existence of an invariant measure for $X$.

  [You may use any general results from the course concerning Markov chains and pure birth processes so long as they are clearly stated.]

  comment

• Paper 1, Section II, K

  Applied Probability

  Part II, 2019

  Let $S$ be a countable set, and let $P=\left(p_{i, j}: i, j \in S\right)$ be a Markov transition matrix with $p_{i, i}=0$ for all $i$. Let $Y=\left(Y_{n}: n=0,1,2, \ldots\right)$ be a discrete-time Markov chain on the state space $S$ with transition matrix $P$.

  The continuous-time process $X=\left(X_{t}: t \geqslant 0\right)$ is constructed as follows. Let $\left(U_{m}: m=0,1,2, \ldots\right)$ be independent, identically distributed random variables having the exponential distribution with mean 1. Let $g$ be a function on $S$ such that $\varepsilon<g(i)<\frac{1}{\varepsilon}$ for all $i \in S$ and some constant $\varepsilon>0$. Let $V_{m}=U_{m} / g\left(Y_{m}\right)$ for $m \geqslant 0$. Let $T_{0}=0$ and $T_{n}=\sum_{m=0}^{n-1} V_{m}$ for $n \geqslant 1$. Finally, let $X_{t}=Y_{n}$ for $T_{n} \leqslant t<T_{n+1}$.

  (a) Explain briefly why $X$ is a continuous-time Markov chain on $S$, and write down its generator in terms of $P$ and the vector $g=(g(i): i \in S)$.

  (b) What does it mean to say that the chain $X$ is irreducible? What does it mean to say a state $i \in S$ is (i) recurrent and (ii) positive recurrent?

  (c) Show that

  (i) $X$ is irreducible if and only if $Y$ is irreducible;

  (ii) $X$ is recurrent if and only if $Y$ is recurrent.

  (d) Suppose $Y$ is irreducible and positive recurrent with invariant distribution $\pi$. Express the invariant distribution of $X$ in terms of $\pi$ and $g$.

  comment

• Paper 4, Section II, A

  Asymptotic Methods

  Part II, 2019

  Consider, for small $\epsilon$, the equation

  $$\epsilon^{2} \frac{d^{2} \psi}{d x^{2}}-q(x) \psi=0$$

  Assume that $(*)$ has bounded solutions with two turning points $a, b$ where $b>a, q^{\prime}(b)>0$ and $q^{\prime}(a)<0$.

  (a) Use the WKB approximation to derive the relationship

  $$\frac{1}{\epsilon} \int_{a}^{b}|q(\xi)|^{1 / 2} d \xi=\left(n+\frac{1}{2}\right) \pi \text { with } n=0,1,2, \cdots$$

  [You may quote without proof any standard results or formulae from WKB theory.]

  (b) In suitable units, the radial Schrödinger equation for a spherically symmetric potential given by $V(r)=-V_{0} / r$, for constant $V_{0}$, can be recast in the standard form $(*)$ as:

  $$\frac{\hbar^{2}}{2 m} \frac{d^{2} \psi}{d x^{2}}+e^{2 x}\left[\lambda-V\left(e^{x}\right)-\frac{\hbar^{2}}{2 m}\left(l+\frac{1}{2}\right)^{2} e^{-2 x}\right] \psi=0$$

  where $r=e^{x}$ and $\epsilon=\hbar / \sqrt{2 m}$ is a small parameter.

  Use result $(* *)$ to show that the energies of the bound states (i.e $\lambda=-|\lambda|<0)$ are approximated by the expression:

  $$E=-|\lambda|=-\frac{m}{2 \hbar^{2}} \frac{V_{0}^{2}}{(n+l+1)^{2}}$$

  [You may use the result

  $$\left.\int_{a}^{b} \frac{1}{r} \sqrt{(r-a)(b-r)} d r=(\pi / 2)[\sqrt{b}-\sqrt{a}]^{2} .\right]$$

  comment

• Paper 3, Section II, A

  Asymptotic Methods

  Part II, 2019

  (a) State Watson's lemma for the case when all the functions and variables involved are real, and use it to calculate the asymptotic approximation as $x \rightarrow \infty$ for the integral $I$, where

  $$I=\int_{0}^{\infty} e^{-x t} \sin \left(t^{2}\right) d t$$

  (b) The Bessel function $J_{\nu}(z)$ of the first kind of order $\nu$ has integral representation

  $$J_{\nu}(z)=\frac{1}{\Gamma\left(\nu+\frac{1}{2}\right) \sqrt{\pi}}\left(\frac{z}{2}\right)^{\nu} \int_{-1}^{1} e^{i z t}\left(1-t^{2}\right)^{\nu-1 / 2} d t$$

  where $\Gamma$ is the Gamma function, $\operatorname{Re}(\nu)>1 / 2$ and $z$ is in general a complex variable. The complex version of Watson's lemma is obtained by replacing $x$ with the complex variable $z$, and is valid for $|z| \rightarrow \infty$ and $|\arg (z)| \leqslant \pi / 2-\delta<\pi / 2$, for some $\delta$ such that $0<\delta<\pi / 2$. Use this version to derive an asymptotic expansion for $J_{\nu}(z)$ as $|z| \rightarrow \infty$. For what values of $\arg (z)$ is this approximation valid?

  [Hint: You may find the substitution $t=2 \tau-1$ useful.]

  comment

• Paper 2, Section II, A

  Asymptotic Methods

  Part II, 2019

  (a) Define formally what it means for a real valued function $f(x)$ to have an asymptotic expansion about $x_{0}$, given by

  $$f(x) \sim \sum_{n=0}^{\infty} f_{n}\left(x-x_{0}\right)^{n} \text { as } x \rightarrow x_{0}$$

  Use this definition to prove the following properties.

  (i) If both $f(x)$ and $g(x)$ have asymptotic expansions about $x_{0}$, then $h(x)=f(x)+g(x)$ also has an asymptotic expansion about $x_{0} .$

  (ii) If $f(x)$ has an asymptotic expansion about $x_{0}$ and is integrable, then

  $$\int_{x_{0}}^{x} f(\xi) d \xi \sim \sum_{n=0}^{\infty} \frac{f_{n}}{n+1}\left(x-x_{0}\right)^{n+1} \text { as } x \rightarrow x_{0}$$

  (b) Obtain, with justification, the first three terms in the asymptotic expansion as $x \rightarrow \infty$ of the complementary error function, $\operatorname{erfc}(x)$, defined as

  $$\operatorname{erfc}(x):=\frac{1}{\sqrt{2 \pi}} \int_{x}^{\infty} e^{-t^{2}} d t$$

  comment

• Paper 1, Section I, H

  Automata and Formal Languages

  Part II, 2019

  (a) State the pumping lemma for context-free languages (CFLs).

  (b) Which of the following are CFLs? Justify your answers.

  (i) $\left\{w w^{R} \mid w \in\{a, b\}^{*}\right\}$, where $w^{R}$ is the reverse of the word $w$.

  (ii) $\left\{0^{p} 1^{p} \mid p\right.$ is a prime $\}$.

  (iii) $\left\{a^{m} b^{n} c^{k} d^{l} \mid 3 m=4 l\right.$ and $\left.2 n=5 k\right\}$.

  (c) Let $L$ and $M$ be CFLs. Show that the concatenation $L M$ is also a CFL.

  comment

• Paper 4, Section I, $4 \mathrm{H}$

  Automata and Formal Languages

  Part II, 2019

  (a) Which of the following are regular languages? Justify your answers.

  (i) $\left\{w^{n} \mid w \in\{a, b\}^{*}, n \geqslant 2\right\}$.

  (ii) $\left\{w \in\{a, b, c\}^{*} \mid w\right.$ contains an odd number of $b$ 's and an even number of $c$ 's $\}$.

  (iii) $\left\{w \in\{0,1\}^{*} \mid w\right.$ contains no more than 7 consecutive 0 's $\}$.

  (b) Consider the language $L$ over alphabet $\{a, b\}$ defined via

  $$L:=\left\{w a b^{n} \mid w \in\{a, b\}^{*}, n \in \mathbb{K}\right\} \cup\{b\}^{*}$$

  Show that $L$ satisfies the pumping lemma for regular languages but is not a regular language itself.

  comment

• Paper 3, Section I, $4 \mathrm{H}$

  Automata and Formal Languages

  Part II, 2019

  (a) Define what it means for a context-free grammar (CFG) to be in Chomsky normal form (CNF). Can a CFG in CNF ever define a language containing $\epsilon$ ? If $G_{\text {Chom }}$ denotes the result of converting an arbitrary CFG $G$ into one in CNF, state the relationship between $\mathcal{L}(G)$ and $\mathcal{L}\left(G_{\text {Chom }}\right)$.

  (b) Let $G$ be a CFG in CNF. Give an algorithm that, on input of any word $v$ on the terminals of $G$, decides if $v \in \mathcal{L}(G)$ or not. Explain why your algorithm works.

  (c) Convert the following CFG $G$ into a grammar in CNF:

  $$\begin{aligned} S \rightarrow & S b b|a S| T \\ & T \rightarrow c c \end{aligned}$$

  Does $\mathcal{L}(G)=\mathcal{L}\left(G_{\text {Chom }}\right)$ in this case? Justify your answer.

  comment

• Paper 2, Section I, H

  Automata and Formal Languages

  Part II, 2019

  (a) Define a recursive set and a recursively enumerable (r.e.) set. Prove that $E \subseteq \mathbb{N}_{0}$ is recursive if and only if both $E$ and $\mathbb{N}_{0} \backslash E$ are r.e. sets.

  (b) Let $E=\left\{f_{n, k}\left(m_{1}, \ldots, m_{k}\right) \mid\left(m_{1}, \ldots, m_{k}\right) \in \mathbb{N}_{0}^{k}\right\}$ for some fixed $k \geqslant 1$ and some fixed register machine code $n$. Show that $E=\left\{m \in \mathbb{N}_{0} \mid f_{j, 1}(m) \downarrow\right\}$ for some fixed register machine code $j$. Hence show that $E$ is an r.e. set.

  (c) Show that the function $f: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}$ defined below is primitive recursive.

  $$f(n)= \begin{cases}n-1 & \text { if } n>0 \\ 0 & \text { if } n=0\end{cases}$$

  [Any use of Church's thesis in your answers should be explicitly stated. In this question $\mathbb{N}_{0}$ denotes the set of non-negative integers.]

  comment

• Paper 1, Section II, H

  Automata and Formal Languages

  Part II, 2019

  Let $D=\left(Q, \Sigma, \delta, q_{0}, F\right)$ be a deterministic finite-state automaton (DFA). Define what it means for two states of $D$ to be equivalent. Define the minimal DFA $D / \sim$ for $D$.

  Let $D$ be a DFA with no inaccessible states, and suppose that $A$ is another DFA on the same alphabet as $D$ and for which $\mathcal{L}(D)=\mathcal{L}(A)$. Show that $A$ has at least as many states as $D / \sim$. [You may use results from the course as long as you state them clearly.]

  Construct a minimal DFA (that is, one with the smallest possible number of states) over the alphabet $\{0,1\}$ which accepts precisely the set of binary numbers which are multiples of 7. You may have leading zeros in your inputs (e.g.: 00101). Prove that your DFA is minimal by finding a distinguishing word for each pair of states.

  comment

• Paper 3, Section II, 12H

  Automata and Formal Languages

  Part II, 2019

  (a) State the $s-m-n$ theorem and the recursion theorem.

  (b) State and prove Rice's theorem.

  (c) Show that if $g: \mathbb{N}_{0}^{2} \rightarrow \mathbb{N}_{0}$ is partial recursive, then there is some $e \in \mathbb{N}_{0}$ such that

  $$f_{e, 1}(y)=g(e, y) \quad \forall y \in \mathbb{N}_{0}$$

  (d) Show there exists some $m \in \mathbb{N}_{0}$ such that $W_{m}$ has exactly $m^{2}$ elements.

  (e) Given $n \in \mathbb{N}_{0}$, is it possible to compute whether or not the number of elements of $W_{n}$ is a (finite) perfect square? Justify your answer.

  [In this question $\mathbb{N}_{0}$ denotes the set of non-negative integers. Any use of Church's thesis in your answers should be explicitly stated.]

  comment

• Paper 4, Section I, E

  Classical Dynamics

  Part II, 2019

  (a) The angular momentum of a rigid body about its centre of mass is conserved.

  Derive Euler's equations,

  $$\begin{aligned} &I_{1} \dot{\omega}_{1}=\left(I_{2}-I_{3}\right) \omega_{2} \omega_{3} \\ &I_{2} \dot{\omega}_{2}=\left(I_{3}-I_{1}\right) \omega_{3} \omega_{1} \\ &I_{3} \dot{\omega}_{3}=\left(I_{1}-I_{2}\right) \omega_{1} \omega_{2} \end{aligned}$$

  explaining the meaning of the quantities appearing in the equations.

  (b) Show that there are two independent conserved quantities that are quadratic functions of $\boldsymbol{\omega}=\left(\omega_{1}, \omega_{2}, \omega_{3}\right)$, and give a physical interpretation of them.

  (c) Derive a linear approximation to Euler's equations that applies when $\left|\omega_{1}\right| \ll\left|\omega_{3}\right|$ and $\left|\omega_{2}\right| \ll\left|\omega_{3}\right|$. Use this to determine the stability of rotation about each of the three principal axes of an asymmetric top.

  comment

• Paper 3, Section I, E

  Classical Dynamics

  Part II, 2019

  A simple harmonic oscillator of mass $m$ and spring constant $k$ has the equation of motion

  $$m \ddot{x}=-k x .$$

  (a) Describe the orbits of the system in phase space. State how the action $I$ of the oscillator is related to a geometrical property of the orbits in phase space. Derive the action-angle variables $(\theta, I)$ and give the form of the Hamiltonian of the oscillator in action-angle variables.

  (b) Suppose now that the spring constant $k$ varies in time. Under what conditions does the theory of adiabatic invariance apply? Assuming that these conditions hold, identify an adiabatic invariant and determine how the energy and amplitude of the oscillator vary with $k$ in this approximation.

  comment

• Paper 2, Section I, E

  Classical Dynamics

  Part II, 2019

  (a) State Hamilton's equations for a system with $n$ degrees of freedom and Hamilto$\operatorname{nian} H(\mathbf{q}, \mathbf{p}, t)$, where $(\mathbf{q}, \mathbf{p})=\left(q_{1}, \ldots, q_{n}, p_{1}, \ldots, p_{n}\right)$ are canonical phase-space variables.

  (b) Define the Poisson bracket $\{f, g\}$ of two functions $f(\mathbf{q}, \mathbf{p}, t)$ and $g(\mathbf{q}, \mathbf{p}, t)$.

  (c) State the canonical commutation relations of the variables $\mathbf{q}$ and $\mathbf{p}$.

  (d) Show that the time-evolution of any function $f(\mathbf{q}, \mathbf{p}, t)$ is given by

  $$\frac{d f}{d t}=\{f, H\}+\frac{\partial f}{\partial t}$$

  (e) Show further that the Poisson bracket of any two conserved quantities is also a conserved quantity.

  [You may assume the Jacobi identity,

  $$\{f,\{g, h\}\}+\{g,\{h, f\}\}+\{h,\{f, g\}\}=0 .]$$

  comment

• Paper 1, Section I, E

  Classical Dynamics

  Part II, 2019

  (a) A mechanical system with $n$ degrees of freedom has the Lagrangian $L(\mathbf{q}, \dot{\mathbf{q}})$, where $\mathbf{q}=\left(q_{1}, \ldots, q_{n}\right)$ are the generalized coordinates and $\dot{\mathbf{q}}=d \mathbf{q} / d t$.

  Suppose that $L$ is invariant under the continuous symmetry transformation $\mathbf{q}(t) \mapsto$ $\mathbf{Q}(s, t)$, where $s$ is a real parameter and $\mathbf{Q}(0, t)=\mathbf{q}(t)$. State and prove Noether's theorem for this system.

  (b) A particle of mass $m$ moves in a conservative force field with potential energy $V(\mathbf{r})$, where $\mathbf{r}$ is the position vector in three-dimensional space.

  Let $(r, \phi, z)$ be cylindrical polar coordinates. $V(\mathbf{r})$ is said to have helical symmetry if it is of the form

  $$V(\mathbf{r})=f(r, \phi-k z),$$

  for some constant $k$. Show that a particle moving in a potential with helical symmetry has a conserved quantity that is a linear combination of angular and linear momenta.

  comment

• Paper 2, Section II, E

  Classical Dynamics

  Part II, 2019

  The Lagrangian of a particle of mass $m$ and charge $q$ moving in an electromagnetic field described by scalar and vector potentials $\phi(\mathbf{r}, t)$ and $\mathbf{A}(\mathbf{r}, t)$ is

  $$L=\frac{1}{2} m|\dot{\mathbf{r}}|^{2}+q(-\phi+\dot{\mathbf{r}} \cdot \mathbf{A})$$

  where $\mathbf{r}(t)$ is the position vector of the particle and $\dot{\mathbf{r}}=d \mathbf{r} / d t$.

  (a) Show that Lagrange's equations are equivalent to the equation of motion

  $$m \ddot{\mathbf{r}}=q(\mathbf{E}+\mathbf{v} \times \mathbf{B}),$$

  where

  $$\mathbf{E}=-\nabla \phi-\frac{\partial \mathbf{A}}{\partial t}, \quad \mathbf{B}=\nabla \times \mathbf{A}$$

  are the electric and magnetic fields.

  (b) Show that the related Hamiltonian is

  $$H=\frac{|\mathbf{p}-q \mathbf{A}|^{2}}{2 m}+q \phi,$$

  where $\mathbf{p}=m \dot{\mathbf{r}}+q \mathbf{A}$. Obtain Hamilton's equations for this system.

  (c) Verify that the electric and magnetic fields remain unchanged if the scalar and vector potentials are transformed according to

  where $f(\mathbf{r}, t)$ is a scalar field. Show that the transformed Lagrangian $\tilde{L}$ differs from $L$ by the total time-derivative of a certain quantity. Why does this leave the form of Lagrange's equations invariant? Show that the transformed Hamiltonian $\tilde{H}$ and phase-space variables $(\mathbf{r}, \tilde{\mathbf{p}})$ are related to $H$ and $(\mathbf{r}, \mathbf{p})$ by a canonical transformation.

  [Hint: In standard notation, the canonical transformation associated with the type-2 generating function $F_{2}(\mathbf{q}, \mathbf{P}, t)$ is given by

  $$\left.\mathbf{p}=\frac{\partial F_{2}}{\partial \mathbf{q}}, \quad \mathbf{Q}=\frac{\partial F_{2}}{\partial \mathbf{P}}, \quad K=H+\frac{\partial F_{2}}{\partial t} .\right]$$

  $$\begin{aligned} & \phi \mapsto \tilde{\phi}=\phi-\frac{\partial f}{\partial t}, \\ & \mathbf{A} \mapsto \tilde{\mathbf{A}}=\mathbf{A}+\nabla f, \end{aligned}$$

  comment

• Paper 4, Section II, E

  Classical Dynamics

  Part II, 2019

  (a) Explain what is meant by a Lagrange top. You may assume that such a top has the Lagrangian

  $$L=\frac{1}{2} I_{1}\left(\dot{\theta}^{2}+\dot{\phi}^{2} \sin ^{2} \theta\right)+\frac{1}{2} I_{3}(\dot{\psi}+\dot{\phi} \cos \theta)^{2}-M g l \cos \theta$$

  in terms of the Euler angles $(\theta, \phi, \psi)$. State the meaning of the quantities $I_{1}, I_{3}, M$ and $l$ appearing in this expression.

  Explain why the quantity

  $$p_{\psi}=\frac{\partial L}{\partial \dot{\psi}}$$

  is conserved, and give two other independent integrals of motion.

  Show that steady precession, with a constant value of $\theta \in\left(0, \frac{\pi}{2}\right)$, is possible if

  $$p_{\psi}^{2} \geqslant 4 M g l I_{1} \cos \theta .$$

  (b) A rigid body of mass $M$ is of uniform density and its surface is defined by

  $$x_{1}^{2}+x_{2}^{2}=x_{3}^{2}-\frac{x_{3}^{3}}{h}$$

  where $h$ is a positive constant and $\left(x_{1}, x_{2}, x_{3}\right)$ are Cartesian coordinates in the body frame.

  Calculate the values of $I_{1}, I_{3}$ and $l$ for this symmetric top, when it rotates about the sharp point at the origin of this coordinate system.

  comment

• Paper 4, Section I, $3 G$

  Coding and Cryptography

  Part II, 2019

  (a) Describe Diffie-Hellman key exchange. Why is it believed to be a secure system?

  (b) Consider the following authentication procedure. Alice chooses public key $N$ for the Rabin-Williams cryptosystem. To be sure we are in communication with Alice we send her a 'random item' $r \equiv m^{2} \bmod N$. On receiving $r$, Alice proceeds to decode using her knowledge of the factorisation of $N$ and finds a square root $m_{1}$ of $r$. She returns $m_{1}$ to us and we check $r \equiv m_{1}^{2} \bmod N$. Is this authentication procedure secure? Justify your answer.

  comment

• Paper 3, Section I, G

  Coding and Cryptography

  Part II, 2019

  What does it mean to transmit reliably at rate $R$ through a binary symmetric channel $(\mathrm{BSC})$ with error probability $p$ ?

  Assuming Shannon's second coding theorem (also known as Shannon's noisy coding theorem), compute the supremum of all possible reliable transmission rates of a BSC. Describe qualitatively the behaviour of the capacity as $p$ varies. Your answer should address the following cases,

  (i) $p$ is small,

  (ii) $p=1 / 2$,

  (iii) $p>1 / 2$.

  comment

• Paper 2, Section I, G

  Coding and Cryptography

  Part II, 2019

  Define the binary Hamming code of length $n=2^{l}-1$ for $l \geqslant 3$. Define a perfect code. Show that a binary Hamming code is perfect.

  What is the weight of the dual code of a binary Hamming code when $l=3 ?$

  comment

• Paper 1, Section I, G

  Coding and Cryptography

  Part II, 2019

  Let $X$ and $Y$ be discrete random variables taking finitely many values. Define the conditional entropy $H(X \mid Y)$. Suppose $Z$ is another discrete random variable taking values in a finite alphabet, and prove that

  $$H(X \mid Y) \leqslant H(X \mid Y, Z)+H(Z)$$

  [You may use the equality $H(X, Y)=H(X \mid Y)+H(Y)$ and the inequality $H(X \mid Y) \leqslant$ $H(X) .]$

  State and prove Fano's inequality.

  comment

• Paper 1, Section II, G

  Coding and Cryptography

  Part II, 2019

  What does it mean to say that $C$ is a binary linear code of length $n$, rank $k$ and minimum distance $d$ ? Let $C$ be such a code.

  (a) Prove that $n \geqslant d+k-1$.

  Let $x=\left(x_{1}, \ldots, x_{n}\right) \in C$ be a codeword with exactly $d$ non-zero digits.

  (b) Prove that puncturing $C$ on the non-zero digits of $x$ produces a code $C^{\prime}$ of length $n-d, \operatorname{rank} k-1$ and minimum distance $d^{\prime}$ for some $d^{\prime} \geqslant\left\lceil\frac{d}{2}\right\rceil$.

  (c) Deduce that $n \geqslant d+\sum_{1 \leqslant l \leqslant k-1}\left\lceil\frac{d}{2^{t}}\right\rceil$.

  comment

• Paper 2, Section II, G

  Coding and Cryptography

  Part II, 2019

  Describe the Huffman coding scheme and prove that Huffman codes are optimal.

  Are the following statements true or false? Justify your answers.

  (i) Given $m$ messages with probabilities $p_{1} \geqslant p_{2} \geqslant \cdots \geqslant p_{m}$ a Huffman coding will assign a unique set of word lengths.

  (ii) An optimal code must be Huffman.

  (iii) Suppose the $m$ words of a Huffman code have word lengths $s_{1}, s_{2}, \ldots, s_{m}$. Then

  $$\sum_{i=1}^{m} 2^{-s_{i}}=1$$

  [Throughout this question you may assume that a decipherable code with prescribed word lengths exists if and only if there is a prefix-free code with the same word lengths.]

  comment

• Paper 3, Section I, B

  Cosmology

  Part II, 2019

  Consider a spherically symmetric distribution of mass with density $\rho(r)$ at distance $r$ from the centre. Derive the pressure support equation that the pressure $P(r)$ has to satisfy for the system to be in static equilibrium.

  Assume now that the mass density obeys $\rho(r)=A r^{2} P(r)$, for some positive constant A. Determine whether or not the system has a stable solution corresponding to a star of finite radius.

  comment

• Paper 4, Section I, B

  Cosmology

  Part II, 2019

  Derive the relation between the neutrino temperature $T_{\nu}$ and the photon temperature $T_{\gamma}$ at a time long after electrons and positrons have become non-relativistic.

  [In this question you may work in units of the speed of light, so that $c=1$. You may also use without derivation the following formulae. The energy density $\epsilon_{a}$ and pressure $P_{a}$ for a single relativistic species a with a number $g_{a}$ of degenerate states at temperature $T$ are given by

  $$\epsilon_{a}=\frac{4 \pi g_{a}}{h^{3}} \int \frac{p^{3} d p}{e^{p /\left(k_{B} T\right)} \mp 1}, \quad \quad P_{a}=\frac{4 \pi g_{a}}{3 h^{3}} \int \frac{p^{3} d p}{e^{p /\left(k_{B} T\right)} \mp 1},$$

  where $k_{B}$ is Boltzmann's constant, $h$ is Planck's constant, and the minus or plus depends on whether the particle is a boson or a fermion respectively. For each species a, the entropy density $s_{a}$ at temperature $T_{a}$ is given by,

  $$s_{a}=\frac{\epsilon_{a}+P_{a}}{k_{B} T_{a}} .$$

  The effective total number $g_{*}$ of relativistic species is defined in terms of the numbers of bosonic and fermionic particles in the theory as,

  $$g_{*}=\sum_{\text {bosons }} g_{\text {bosons }}+\frac{7}{8} \sum_{\text {fermions }} g_{\text {fermions }}$$

  with the specific values $g_{\gamma}=g_{e^{+}}=g_{e^{-}}=2$ for photons, positrons and electrons.]

  comment

• Paper 1, Section I, B

  Cosmology

  Part II, 2019

  [You may work in units of the speed of light, so that $c=1$.]

  By considering a spherical distribution of matter with total mass $M$ and radius $R$ and an infinitesimal mass $\delta m$ located somewhere on its surface, derive the Friedmann equation describing the evolution of the scale factor $a(t)$ appearing in the relation $R(t)=R_{0} a(t) / a\left(t_{0}\right)$ for a spatially-flat FLRW spacetime.

  Consider now a spatially-flat, contracting universe filled by a single component with energy density $\rho$, which evolves with time as $\rho(t)=\rho_{0}\left[a(t) / a\left(t_{0}\right)\right]^{-4}$. Solve the Friedmann equation for $a(t)$ with $a\left(t_{0}\right)=1$.

  comment

• Paper 2, Section I, B

  Cosmology

  Part II, 2019

  [You may work in units of the speed of light, so that $c=1$.]

  (a) Combining the Friedmann and continuity equations

  $$H^{2}=\frac{8 \pi G}{3} \rho, \quad \dot{\rho}+3 H(\rho+P)=0$$

  derive the Raychaudhuri equation (also known as the acceleration equation) which expresses $\ddot{a} / a$ in terms of the energy density $\rho$ and the pressure $P$.

  (b) Assuming an equation of state $P=w \rho$ with constant $w$, for what $w$ is the expansion of the universe accelerated or decelerated?

  (c) Consider an expanding, spatially-flat FLRW universe with both a cosmological constant and non-relativistic matter (also known as dust) with energy densities $\rho_{c c}$ and $\rho_{d u s t}$ respectively. At some time corresponding to $a_{e q}$, the energy densities of these two components are equal $\rho_{c c}\left(a_{e q}\right)=\rho_{d u s t}\left(a_{e q}\right)$. Is the expansion of the universe accelerated or decelerated at this time?

  (d) For what numerical value of $a / a_{e q}$ does the universe transition from deceleration to acceleration?

  comment

• Paper 3, Section II, B

  Cosmology

  Part II, 2019

  [You may work in units of the speed of light, so that $c=1 .$ ]

  Consider the process where protons and electrons combine to form neutral hydrogen atoms;

  $$p^{+}+e^{-} \leftrightarrow H^{0}+\gamma$$

  Let $n_{p}, n_{e}$ and $n_{H}$ denote the number densities for protons, electrons and hydrogen atoms respectively. The ionization energy of hydrogen is denoted $I$. State and derive $S a h a$ 's equation for the ratio $n_{e} n_{p} / n_{H}$, clearly describing the steps required.

  [You may use without proof the following formula for the equilibrium number density of a non-relativistic species $a$ with $g_{a}$ degenerate states of mass $m$ at temperature $T$ such that $k_{B} T \ll m$,

  $$n_{a}=g_{a}\left(\frac{2 \pi m k_{B} T}{h^{2}}\right)^{3 / 2} \exp \left([\mu-m] / k_{B} T\right)$$

  where $\mu$ is the chemical potential and $k_{B}$ and $h$ are the Boltzmann and Planck constants respectively.]

  The photon number density $n_{\gamma}$ is given as

  $$n_{\gamma}=\frac{16 \pi}{h^{3}} \zeta(3)\left(k_{B} T\right)^{3}$$

  where $\zeta(3) \simeq 1.20$. Consider now the fractional ionization $X_{e}=n_{e} /\left(n_{e}+n_{H}\right)$. In our universe $n_{e}+n_{H}=n_{p}+n_{H} \simeq \eta n_{\gamma}$ where $\eta$ is the baryon-to-photon number ratio. Find an expression for the ratio

  $$\frac{\left(1-X_{e}\right)}{X_{e}^{2}}$$

  in terms of $k_{B} T, \eta, I$ and the particle masses. One might expect neutral hydrogen to form at a temperature given by $k_{B} T \sim I \sim 13 \mathrm{eV}$, but instead in our universe it forms at the much lower temperature $k_{B} T \sim 0.3 \mathrm{eV}$. Briefly explain why this happens. Estimate the temperature at which neutral hydrogen would form in a hypothetical universe with $\eta=1$. Briefly explain your answer.

  comment

• Paper 1, Section II, 15B

  Cosmology

  Part II, 2019

  [You may work in units of the speed of light, so that $c=1$.]

  Consider a spatially-flat FLRW universe with a single, canonical, homogeneous scalar field $\phi(t)$ with a potential $V(\phi)$. Recall the Friedmann equation and the Raychaudhuri equation (also known as the acceleration equation)

  $$\begin{aligned} \left(\frac{\dot{a}}{a}\right)^{2} &=H^{2}=\frac{8 \pi G}{3}\left[\frac{1}{2} \dot{\phi}^{2}+V\right] \\ \frac{\ddot{a}}{a} &=-\frac{8 \pi G}{3}\left(\dot{\phi}^{2}-V\right) \end{aligned}$$

  (a) Assuming $\dot{\phi} \neq 0$, derive the equations of motion for $\phi$, i.e.

  $$\ddot{\phi}+3 H \dot{\phi}+\partial_{\phi} V=0 .$$

  (b) Assuming the special case $V(\phi)=\lambda \phi^{4}$, find $\phi(t)$, for some initial value $\phi\left(t_{0}\right)=\phi_{0}$ in the slow-roll approximation, i.e. assuming that $\dot{\phi}^{2} \ll 2 V$ and $\ddot{\phi} \ll 3 H \dot{\phi}$.

  (c) The number $N$ of efoldings is defined by $d N=d \ln a$. Using the chain rule, express $d N$ first in terms of $d t$ and then in terms of $d \phi$. Write the resulting relation between $d N$ and $d \phi$ in terms of $V$ and $\partial_{\phi} V$ only, using the slow-roll approximation.

  (d) Compute the number $N$ of efoldings of expansion between some initial value $\phi_{i}<0$ and a final value $\phi_{f}<0$ (so that $\dot{\phi}>0$ throughout).

  (e) Discuss qualitatively the horizon and flatness problems in the old hot big bang model (i.e. without inflation) and how inflation addresses them.

  comment

• Paper 4, Section II, H

  Differential Geometry

  Part II, 2019

  (a) Let $\gamma:(a, b) \rightarrow \mathbb{R}^{2}$ be a regular curve without self-intersection given by $\gamma(v)=(f(v), g(v))$ with $f(v)>0$ for $v \in(a, b)$ and let $S$ be the surface of revolution defined globally by the parametrisation

  $$\phi:(0,2 \pi) \times(a, b) \rightarrow \mathbb{R}^{3}$$

  where $\phi(u, v)=(f(v) \cos u, f(v) \sin u, g(v))$, i.e. $S=\phi((0,2 \pi) \times(a, b))$. Compute its mean curvature $H$ and its Gaussian curvature $K$.

  (b) Define what it means for a regular surface $S \subset \mathbb{R}^{3}$ to be minimal. Give an example of a minimal surface which is not locally isometric to a cone, cylinder or plane. Justify your answer.

  (c) Let $S$ be a regular surface such that $K \equiv 1$. Is it necessarily the case that given any $p \in S$, there exists an open neighbourhood $\mathcal{U} \subset S$ of $p$ such that $\mathcal{U}$ lies on some sphere in $\mathbb{R}^{3}$ ? Justify your answer.

  comment

• Paper 3, Section II, H

  Differential Geometry

  Part II, 2019

  (a) Let $\alpha:(a, b) \rightarrow \mathbb{R}^{2}$ be a regular curve without self intersection given by $\alpha(v)=(f(v), g(v))$ with $f(v)>0$ for $v \in(a, b)$.

  Consider the local parametrisation given by

  $$\phi:(0,2 \pi) \times(a, b) \rightarrow \mathbb{R}^{3}$$

  where $\phi(u, v)=(f(v) \cos u, f(v) \sin u, g(v))$.

  (i) Show that the image $\phi((0,2 \pi) \times(a, b))$ defines a regular surface $S$ in $\mathbb{R}^{3}$.

  (ii) If $\gamma(s)=\phi(u(s), v(s))$ is a geodesic in $S$ parametrised by arc length, then show that $f(v(s))^{2} u^{\prime}(s)$ is constant in $s$. If $\theta(s)$ denotes the angle that the geodesic makes with the parallel $S \cap\{z=g(v(s))\}$, then show that $f(v(s)) \cos \theta(s)$ is constant in $s$.

  (b) Now assume that $\alpha(v)=(f(v), g(v))$ extends to a smooth curve $\alpha:[a, b] \rightarrow \mathbb{R}^{2}$ such that $f(a)=0, f(b)=0, f^{\prime}(a) \neq 0, f^{\prime}(b) \neq 0$. Let $\bar{S}$ be the closure of $S$ in $\mathbb{R}^{3}$.

  (i) State a necessary and sufficient condition on $\alpha(v)$ for $\bar{S}$ to be a compact regular surface. Justify your answer.

  (ii) If $\bar{S}$ is a compact regular surface, and $\gamma:(-\infty, \infty) \rightarrow \bar{S}$ is a geodesic, show that there exists a non-empty open subset $U \subset \bar{S}$ such that $\gamma((-\infty, \infty)) \cap U=\emptyset$.

  comment

• Paper 2, Section II, H

  Differential Geometry

  Part II, 2019

  (a) Let $\alpha:(a, b) \rightarrow \mathbb{R}^{3}$ be a smooth regular curve parametrised by arclength. For $s \in(a, b)$, define the curvature $k(s)$ and (where defined) the torsion $\tau(s)$ of $\alpha$. What condition must be satisfied in order for the torsion to be defined? Derive the Frenet equations.

  (b) If $\tau(s)$ is defined and equal to 0 for all $s \in(a, b)$, show that $\alpha$ lies in a plane.

  (c) State the fundamental theorem for regular curves in $\mathbb{R}^{3}$, giving necessary and sufficient conditions for when curves $\alpha(s)$ and $\widetilde{\alpha}(s)$ are related by a proper Euclidean motion.

  (d) Now suppose that $\widetilde{\alpha}:(a, b) \rightarrow \mathbb{R}^{3}$ is another smooth regular curve parametrised by arclength, and that $\widetilde{k}(s)$ and $\tilde{\tau}(s)$ are its curvature and torsion. Determine whether the following statements are true or false. Justify your answer in each case.

  (i) If $\tau(s)=0$ whenever it is defined, then $\alpha$ lies in a plane.

  (ii) If $\tau(s)$ is defined and equal to 0 for all but one value of $s$ in $(a, b)$, then $\alpha$ lies in a plane.

  (iii) If $k(s)=\tilde{k}(s)$ for all $s, \tau(s)$ and $\tilde{\tau}(s)$ are defined for all $s \neq s_{0}$, and $\tau(s)=\tilde{\tau}(s)$ for all $s \neq s_{0}$, then $\alpha$ and $\widetilde{\alpha}$ are related by a rigid motion.

  comment

• Paper 1, Section II, H

  Differential Geometry

  Part II, 2019

  Let $n \geqslant 1$ be an integer.

  (a) Show that $\mathbb{S}^{n}=\left\{x \in \mathbb{R}^{n+1}: x_{1}^{2}+\cdots+x_{n+1}^{2}=1\right\}$ defines a submanifold of $\mathbb{R}^{n+1}$ and identify explicitly its tangent space $T_{x} \mathbb{S}^{n}$ for any $x \in \mathbb{S}^{n}$.

  (b) Show that the matrix group $S O(n) \subset \mathbb{R}^{n^{2}}$ defines a submanifold. Identify explicitly the tangent space $T_{R} S O(n)$ for any $R \in S O(n)$.

  (c) Given $v \in \mathbb{S}^{n}$, show that the set $S_{v}=\{R \in S O(n+1): R v=v\}$ defines a submanifold $S_{v} \subset S O(n+1)$ and compute its dimension. For $v \neq w$, is it ever the case that $S_{v}$ and $S_{w}$ are transversal?

  [You may use standard theorems from the course concerning regular values and transversality.]

  comment

• Paper 4, Section II, E

  Dynamical Systems

  Part II, 2019

  Consider the dynamical system

  $$\begin{aligned} &\dot{x}=x+y^{2}-a \\ &\dot{y}=y\left(4 x-x^{2}-a\right) \end{aligned}$$

  for $(x, y) \in \mathbb{R}^{2}, a \in \mathbb{R}$.

  Find all fixed points of this system. Find the three different values of $a$ at which bifurcations appear. For each such value give the location $(x, y)$ of all bifurcations. For each of these, what types of bifurcation are suggested from this analysis?

  Use centre manifold theory to analyse these bifurcations. In particular, for each bifurcation derive an equation for the dynamics on the extended centre manifold and hence classify the bifurcation.

  comment

• Paper 3, Section II, E

  Dynamical Systems

  Part II, 2019

  Consider a dynamical system of the form

  $$\begin{aligned} &\dot{x}=x(1-y+a x) \\ &\dot{y}=r y(-1+x-b y) \end{aligned}$$

  on $\Lambda=\{(x, y): x>0$ and $y>0\}$, where $a, b$ and $r$ are real constants and $r>0$.

  (a) For $a=b=0$, by considering a function of the form $V(x, y)=f(x)+g(y)$, show that all trajectories in $\Lambda$ are either periodic orbits or a fixed point.

  (b) Using the same $V$, show that no periodic orbits in $\Lambda$ persist for small $a$ and $b$ if $a b<0$.

  [Hint: for $a=b=0$ on the periodic orbits with period $T$, show that $\int_{0}^{T}(1-x) d t=0$ and hence that $\int_{0}^{T} x(1-x) d t=\int_{0}^{T}\left[-(1-x)^{2}+(1-x)\right] d t<0$.]

  (c) By considering Dulac's criterion with $\phi=1 /(x y)$, show that there are no periodic orbits in $\Lambda$ if $a b<0$.

  (d) Purely by consideration of the existence of fixed points in $\Lambda$ and their Poincaré indices, determine those $(a, b)$ for which the possibility of periodic orbits can be excluded.

  (e) Combining the results above, sketch the $a-b$ plane showing where periodic orbits in $\Lambda$ might still be possible.

  comment

• Paper 2, Section II, E

  Dynamical Systems

  Part II, 2019

  For a map $F: \Lambda \rightarrow \Lambda$ give the definitions of chaos according to (i) Devaney (Dchaos) and (ii) Glendinning (G-chaos).

  Consider the dynamical system

  $$F(x)=a x \quad(\bmod 1)$$

  on $\Lambda=[0,1)$, for $a>1$ (note that $a$ is not necessarily an integer). For both definitions of chaos, show that this system is chaotic.

  comment

• Paper 1, Section II, E

  Dynamical Systems

  Part II, 2019

  For a dynamical system of the form $\dot{\mathbf{x}}=\mathbf{f}(\mathbf{x})$, give the definition of the alpha-limit set $\alpha(\mathbf{x})$ and the omega-limit set $\omega(\mathbf{x})$ of a point $\mathbf{x}$.

  Consider the dynamical system

  $$\begin{aligned} &\dot{x}=x^{2}-1, \\ &\dot{y}=k x y, \end{aligned}$$

  where $\mathbf{x}=(x, y) \in \mathbb{R}^{2}$ and $k$ is a real constant. Answer the following for all values of $k$, taking care over boundary cases (both in $k$ and in $\mathbf{x}$ ).

  (i) What symmetries does this system have?

  (ii) Find and classify the fixed points of this system.

  (iii) Does this system have any periodic orbits?

  (iv) Give $\alpha(\mathbf{x})$ and $\omega(\mathbf{x})$ (considering all $\mathbf{x} \in \mathbb{R}^{2}$ ).

  (v) For $\mathbf{x}_{0}=\left(0, y_{0}\right)$, give the orbit of $\mathbf{x}_{0}$ (considering all $y_{0} \in \mathbb{R}$ ). You should give your answer in the form $y=y\left(x, y_{0}, k\right)$, and specify the range of $x$.

  comment

• Paper 4, Section II, E

  Electrodynamics

  Part II, 2019

  Consider a medium in which the electric displacement $\mathbf{D}(t, \mathbf{x})$ and magnetising field $\mathbf{H}(t, \mathbf{x})$ are linearly related to the electric and magnetic fields respectively with corresponding polarisation constants $\varepsilon$ and $\mu$;

  $$\mathbf{D}=\varepsilon \mathbf{E}, \quad \mathbf{B}=\mu \mathbf{H} .$$

  Write down Maxwell's equations for $\mathbf{E}, \mathbf{B}, \mathbf{D}$ and $\mathbf{H}$ in the absence of free charges and currents.

  Consider EM waves of the form,

  $$\begin{aligned} &\mathbf{E}(t, \mathbf{x})=\mathbf{E}_{0} \sin (\mathbf{k} \cdot \mathbf{x}-\omega t) \\ &\mathbf{B}(t, \mathbf{x})=\mathbf{B}_{0} \sin (\mathbf{k} \cdot \mathbf{x}-\omega t) \end{aligned}$$

  Find conditions on the electric and magnetic polarisation vectors $\mathbf{E}_{0}$ and $\mathbf{B}_{0}$, wave-vector $\mathbf{k}$ and angular frequency $\omega$ such that these fields satisfy Maxwell's equations for the medium described above. At what speed do the waves propagate?

  Consider two media, filling the regions $x<0$ and $x>0$ in three dimensional space, and having two different values $\varepsilon_{-}$and $\varepsilon_{+}$of the electric polarisation constant. Suppose an electromagnetic wave is incident from the region $x<0$ resulting in a transmitted wave in the region $x>0$ and also a reflected wave for $x<0$. The angles of incidence, reflection and transmission are denoted $\theta_{I}, \theta_{R}$ and $\theta_{T}$ respectively. By constructing a corresponding solution of Maxwell's equations, derive the law of reflection $\theta_{I}=\theta_{R}$ and Snell's law of refraction, $n_{-} \sin \theta_{I}=n_{+} \sin \theta_{T}$ where $n_{\pm}=c \sqrt{\varepsilon_{\pm} \mu}$ are the indices of refraction of the two media.

  Consider the special case in which the electric polarisation vectors $\mathbf{E}_{I}, \mathbf{E}_{R}$ and $\mathbf{E}_{T}$ of the incident, reflected and transmitted waves are all normal to the plane of incidence (i.e. the plane containing the corresponding wave-vectors). By imposing appropriate boundary conditions for $\mathbf{E}$ and $\mathbf{H}$ at $x=0$, show that,

  $$\frac{\left|\mathbf{E}_{R}\right|}{\left|\mathbf{E}_{T}\right|}=\frac{1}{2}\left(1-\frac{\tan \theta_{R}}{\tan \theta_{T}}\right)$$

  comment

• Paper 3, Section II, E

  Electrodynamics

  Part II, 2019

  A time-dependent charge distribution $\rho(t, \mathbf{x})$ localised in some region of size $a$ near the origin varies periodically in time with characteristic angular frequency $\omega$. Explain briefly the circumstances under which the dipole approximation for the fields sourced by the charge distribution is valid.

  Far from the origin, for $r=|\mathbf{x}| \gg a$, the vector potential $\mathbf{A}(t, \mathbf{x})$ sourced by the charge distribution $\rho(t, \mathbf{x})$ is given by the approximate expression

  $$\mathbf{A}(t, \mathbf{x}) \simeq \frac{\mu_{0}}{4 \pi r} \int d^{3} \mathbf{x}^{\prime} \mathbf{J}\left(t-r / c, \mathbf{x}^{\prime}\right),$$

  where $\mathbf{J}(t, \mathbf{x})$ is the corresponding current density. Show that, in the dipole approximation, the large-distance behaviour of the magnetic field is given by,

  $$\mathbf{B}(t, \mathbf{x}) \simeq-\frac{\mu_{0}}{4 \pi r c} \hat{\mathbf{x}} \times \ddot{\mathbf{p}}(t-r / c)$$

  where $\mathbf{p}(t)$ is the electric dipole moment of the charge distribution. Assuming that, in the same approximation, the corresponding electric field is given as $\mathbf{E}=-c \hat{\mathbf{x}} \times \mathbf{B}$, evaluate the flux of energy through the surface element of a large sphere of radius $R$ centred at the origin. Hence show that the total power $P(t)$ radiated by the charge distribution is given by

  $$P(t)=\frac{\mu_{0}}{6 \pi c}|\ddot{\mathbf{p}}(t-R / c)|^{2}$$

  A particle of charge $q$ and mass $m$ undergoes simple harmonic motion in the $x$-direction with time period $T=2 \pi / \omega$ and amplitude $\mathcal{A}$ such that

  $$\mathbf{x}(t)=\mathcal{A} \sin (\omega t) \mathbf{i}_{x}$$

  Here $\mathbf{i}_{x}$ is a unit vector in the $x$-direction. Calculate the total power $P(t)$ radiated through a large sphere centred at the origin in the dipole approximation and determine its time averaged value,

  $$\langle P\rangle=\frac{1}{T} \int_{0}^{T} P(t) d t .$$

  For what values of the parameters $\mathcal{A}$ and $\omega$ is the dipole approximation valid?

  Now suppose that the energy of the particle with trajectory $(\star)$ is given by the usual non-relativistic formula for a harmonic oscillator i.e. $E=m|\dot{\mathbf{x}}|^{2} / 2+m \omega^{2}|\mathbf{x}|^{2} / 2$, and that the particle loses energy due to the emission of radiation at a rate corresponding to the time-averaged power $\langle P\rangle$. Work out the half-life of this system (i.e. the time $t_{1 / 2}$ such that $\left.E\left(t_{1 / 2}\right)=E(0) / 2\right)$. Explain why the non-relativistic approximation for the motion of the particle is reliable as long as the dipole approximation is valid.

  comment

• Paper 1, Section II, E

  Electrodynamics

  Part II, 2019

  A relativistic particle of charge $q$ and mass $m$ moves in a background electromagnetic field. The four-velocity $u^{\mu}(\tau)$ of the particle at proper time $\tau$ is determined by the equation of motion,

  $$m \frac{d u^{\mu}}{d \tau}=q F_{\nu}^{\mu} u^{\nu} .$$

  Here $F_{\nu}^{\mu}=\eta_{\nu \rho} F^{\mu \rho}$, where $F_{\mu \nu}$ is the electromagnetic field strength tensor and Lorentz indices are raised and lowered with the metric tensor $\eta=\operatorname{diag}\{-1,+1,+1,+1\}$. In the case of a constant, homogeneous field, write down the solution of this equation giving $u^{\mu}(\tau)$ in terms of its initial value $u^{\mu}(0)$.

  [In the following you may use the relation, given below, between the components of the field strength tensor $F_{\mu \nu}$, for $\mu, \nu=0,1,2,3$, and those of the electric and magnetic fields $\mathbf{E}=\left(E_{1}, E_{2}, E_{3}\right)$ and $\mathbf{B}=\left(B_{1}, B_{2}, B_{3}\right)$,

  $$F_{i 0}=-F_{0 i}=\frac{1}{c} E_{i}, \quad F_{i j}=\varepsilon_{i j k} B_{k}$$

  for $i, j=1,2,3 .]$

  Suppose that, in some inertial frame with spacetime coordinates $\mathbf{x}=(x, y, z)$ and $t$, the electric and magnetic fields are parallel to the $x$-axis with magnitudes $E$ and $B$ respectively. At time $t=\tau=0$ the 3 -velocity $\mathbf{v}=d \mathbf{x} / d t$ of the particle has initial value $\mathbf{v}(0)=\left(0, v_{0}, 0\right)$. Find the subsequent trajectory of the particle in this frame, giving coordinates $x, y, z$ and $t$ as functions of the proper time $\tau$.

  Find the motion in the $x$-direction explicitly, giving $x$ as a function of coordinate time $t$. Comment on the form of the solution at early and late times. Show that, when projected onto the $y-z$ plane, the particle undergoes circular motion which is periodic in proper time. Find the radius $R$ of the circle and proper time period of the motion $\Delta \tau$ in terms of $q, m, E, B$ and $v_{0}$. The resulting trajectory therefore has the form of a helix with varying pitch $P_{n}:=\Delta x_{n} / R$ where $\Delta x_{n}$ is the distance in the $x$-direction travelled by the particle during the $n$ 'th period of its motion in the $y-z$ plane. Show that, for $n \gg 1$,

  $$P_{n} \sim A \exp \left(\frac{2 \pi E n}{c B}\right),$$

  where $A$ is a constant which you should determine.

  comment

• Paper 4, Section II, A

  Fluid Dynamics

  Part II, 2019

  (a) Show that the Stokes flow around a rigid moving sphere has the minimum viscous dissipation rate of all incompressible flows which satisfy the no-slip boundary conditions on the sphere.

  (b) Let $\boldsymbol{u}=\boldsymbol{\nabla}(\boldsymbol{x} \cdot \boldsymbol{\Phi}+\chi)-2 \boldsymbol{\Phi}$, where $\boldsymbol{\Phi}$ and $\chi$ are solutions of Laplace's equation, i.e. $\nabla^{2} \boldsymbol{\Phi}=\mathbf{0}$ and $\nabla^{2} \chi=0$.

  (i) Show that $\boldsymbol{u}$ is incompressible.

  (ii) Show that $\boldsymbol{u}$ satisfies Stokes equation if the pressure $p=2 \mu \boldsymbol{\nabla} \cdot \boldsymbol{\Phi}$.

  (c) Consider a rigid sphere moving with velocity $\boldsymbol{U}$. The Stokes flow around the sphere is given by

  $$\boldsymbol{\Phi}=\alpha \frac{\boldsymbol{U}}{r} \quad \text { and } \quad \chi=\beta \boldsymbol{U} \cdot \boldsymbol{\nabla}\left(\frac{1}{r}\right)$$

  where the origin is chosen to be at the centre of the sphere. Find the values for $\alpha$ and $\beta$ which ensure no-slip conditions are satisfied on the sphere.

  comment

• Paper 2, Section II, A

  Fluid Dynamics

  Part II, 2019

  A viscous fluid is contained in a channel between rigid planes $y=-h$ and $y=h$. The fluid in the upper region $\sigma<y<h$ (with $-h<\sigma<h$ ) has dynamic viscosity $\mu_{-}$ while the fluid in the lower region $-h<y<\sigma$ has dynamic viscosity $\mu_{+}>\mu_{-}$. The plane at $y=h$ moves with velocity $U_{-}$and the plane at $y=-h$ moves with velocity $U_{+}$, both in the $x$ direction. You may ignore the effect of gravity.

  (a) Find the steady, unidirectional solution of the Navier-Stokes equations in which the interface between the two fluids remains at $y=\sigma$.

  (b) Using the solution from part (a):

  (i) calculate the stress exerted by the fluids on the two boundaries;

  (ii) calculate the total viscous dissipation rate in the fluids;

  (iii) demonstrate that the rate of working by boundaries balances the viscous dissipation rate in the fluids.

  (c) Consider the situation where $U_{+}+U_{-}=0$. Defining the volume flux in the upper region as $Q_{-}$and the volume flux in the lower region as $Q_{+}$, show that their ratio is independent of $\sigma$ and satisfies

  $$\frac{Q_{-}}{Q_{+}}=-\frac{\mu_{-}}{\mu_{+}}$$

  comment

• Paper 3, Section II, A

  Fluid Dynamics

  Part II, 2019

  For a fluid with kinematic viscosity $\nu$, the steady axisymmetric boundary-layer equations for flow primarily in the $z$-direction are

  $$\begin{aligned} u \frac{\partial w}{\partial r}+w \frac{\partial w}{\partial z} &=\frac{\nu}{r} \frac{\partial}{\partial r}\left(r \frac{\partial w}{\partial r}\right) \\ \frac{1}{r} \frac{\partial(r u)}{\partial r}+\frac{\partial w}{\partial z} &=0 \end{aligned}$$

  where $u$ is the fluid velocity in the $r$-direction and $w$ is the fluid velocity in the $z$-direction. A thin, steady, axisymmetric jet emerges from a point at the origin and flows along the $z$-axis in a fluid which is at rest far from the $z$-axis.

  (a) Show that the momentum flux

  $$M:=\int_{0}^{\infty} r w^{2} d r$$

  is independent of the position $z$ along the jet. Deduce that the thickness $\delta(z)$ of the jet increases linearly with $z$. Determine the scaling dependence on $z$ of the centre-line velocity $W(z)$. Hence show that the jet entrains fluid.

  (b) A similarity solution for the streamfunction,

  $$\psi(x, y, z)=\nu z g(\eta) \quad \text { with } \quad \eta:=r / z$$

  exists if $g$ satisfies the second order differential equation

  $$\eta g^{\prime \prime}-g^{\prime}+g g^{\prime}=0$$

  Using appropriate boundary and normalisation conditions (which you should state clearly) to solve this equation, show that

  $$g(\eta)=\frac{12 M \eta^{2}}{32 \nu^{2}+3 M \eta^{2}}$$

  comment

• Paper 1, Section II, A

  Fluid Dynamics

  Part II, 2019

  A disc of radius $R$ and weight $W$ hovers at a height $h$ on a cushion of air above a horizontal air table - a fine porous plate through which air of density $\rho$ and dynamic viscosity $\mu$ is pumped upward at constant speed $V$. You may assume that the air flow is axisymmetric with no flow in the azimuthal direction, and that the effect of gravity on the air may be ignored.

  (a) Write down the relevant components of the Navier-Stokes equations. By estimating the size of the individual terms, simplify these equations when $\varepsilon:=h / R \ll 1$ and $R e:=\rho V h / \mu \ll 1$.

  (b) Explain briefly why it is reasonable to expect that the vertical velocity of the air below the disc is a function of distance above the air table alone, and thus find the steady pressure distribution below the disc. Hence show that

  $$W=\frac{3 \pi \mu V R}{2 \varepsilon^{3}}$$

  comment

• Paper 4, Section I, A

  Further Complex Methods

  Part II, 2019

  A single-valued function $\operatorname{Arcsin}(z)$ can be defined, for $0 \leqslant \arg z<2 \pi$, by means of an integral as:

  $$\operatorname{Arcsin}(z)=\int_{0}^{z} \frac{d t}{\left(1-t^{2}\right)^{1 / 2}}$$

  (a) Choose a suitable branch-cut with the integrand taking a value $+1$ at the origin on the upper side of the cut, i.e. at $t=0^{+}$, and describe suitable paths of integration in the two cases $0 \leqslant \arg z \leqslant \pi$ and $\pi<\arg z<2 \pi$.

  (b) Construct the multivalued function $\arcsin (z)$ by analytic continuation.

  (c) Express arcsin $\left(e^{2 \pi i} z\right)$ in terms of $\operatorname{Arcsin}(z)$ and deduce the periodicity property of $\sin (z)$.

  comment

• Paper 3, Section I, A

  Further Complex Methods

  Part II, 2019

  The equation

  $$z w^{\prime \prime}+w=0$$

  has solutions of the form

  $$w(z)=\int_{\gamma} e^{z t} f(t) d t$$

  for suitably chosen contours $\gamma$ and some suitable function $f(t)$.

  (a) Find $f(t)$ and determine the required condition on $\gamma$, which you should express in terms of $z$ and $t$.

  (b) Use the result of part (a) to specify a possible contour with the help of a clearly labelled diagram.

  comment

• Paper 2, Section I, A

  Further Complex Methods

  Part II, 2019

  Assume that $|f(z) / z| \rightarrow 0$ as $|z| \rightarrow \infty$ and that $f(z)$ is analytic in the upper half-plane (including the real axis). Evaluate

  $$\mathcal{P} \int_{-\infty}^{\infty} \frac{f(x)}{x\left(x^{2}+a^{2}\right)} d x$$

  where $a$ is a positive real number.

  [You must state clearly any standard results involving contour integrals that you use.]

  comment

• Paper 1, Section I, A

  Further Complex Methods

  Part II, 2019

  The Beta function is defined by

  $$B(p, q):=\int_{0}^{1} t^{p-1}(1-t)^{q-1} d t=\frac{\Gamma(p) \Gamma(q)}{\Gamma(p+q)}$$

  where $\operatorname{Re} p>0, \operatorname{Re} q>0$, and $\Gamma$ is the Gamma function.

  (a) By using a suitable substitution and properties of Beta and Gamma functions, show that

  $$\int_{0}^{1} \frac{d x}{\sqrt{1-x^{4}}}=\frac{[\Gamma(1 / 4)]^{2}}{\sqrt{32 \pi}}$$

  (b) Deduce that

  $$K(1 / \sqrt{2})=\frac{4[\Gamma(5 / 4)]^{2}}{\sqrt{\pi}}$$

  where $K(k)$ is the complete elliptic integral, defined as

  $$K(k):=\int_{0}^{1} \frac{d t}{\sqrt{\left(1-t^{2}\right)\left(1-k^{2} t^{2}\right)}}$$

  [Hint: You might find the change of variable $x=t\left(2-t^{2}\right)^{-1 / 2}$ helpful in part (b).]

  comment

• Paper 2, Section II, A

  Further Complex Methods

  Part II, 2019

  The Riemann zeta function is defined as

  $$\zeta(z):=\sum_{n=1}^{\infty} \frac{1}{n^{z}}$$

  for $R e(z)>1$, and by analytic continuation to the rest of $\mathbb{C}$ except at singular points. The integral representation of ( $\dagger$ ) for $\operatorname{Re}(z)>1$ is given by

  $$\zeta(z)=\frac{1}{\Gamma(z)} \int_{0}^{\infty} \frac{t^{z-1}}{e^{t}-1} d t$$

  where $\Gamma$ is the Gamma function.

  (a) The Hankel representation is defined as

  $$\zeta(z)=\frac{\Gamma(1-z)}{2 \pi i} \int_{-\infty}^{\left(0^{+}\right)} \frac{t^{z-1}}{e^{-t}-1} d t$$

  Explain briefly why this representation gives an analytic continuation of $\zeta(z)$ as defined in ( $\ddagger$ ) to all $z$ other than $z=1$, using a diagram to illustrate what is meant by the upper limit of the integral in $(\star)$.

  [You may assume $\Gamma(z) \Gamma(1-z)=\pi / \sin (\pi z)$.]

  (b) Find

  $$\operatorname{Res}\left(\frac{t^{-z}}{e^{-t}-1}, t=2 \pi i n\right)$$

  where $n$ is an integer and the poles are simple.

  (c) By considering

  $$\int_{\gamma} \frac{t^{-z}}{e^{-t}-1} d t$$

  where $\gamma$ is a suitably modified Hankel contour and using the result of part (b), derive the reflection formula:

  $$\zeta(1-z)=2^{1-z} \pi^{-z} \cos \left(\frac{1}{2} \pi z\right) \Gamma(z) \zeta(z)$$

  comment

• Paper 1, Section II, A

  Further Complex Methods

  Part II, 2019

  (a) Consider the Papperitz symbol (or P-symbol):

  $$P\left\{\begin{array}{cccc} a & b & c & \\ \alpha & \beta & \gamma & z \\ \alpha^{\prime} & \beta^{\prime} & \gamma^{\prime} & \end{array}\right\}$$

  Explain in general terms what this $P$-symbol represents.

  [You need not write down any differential equations explicitly, but should provide an explanation of the meaning of $a, b, c, \alpha, \beta, \gamma, \alpha^{\prime}, \beta^{\prime}$ and $\left.\gamma^{\prime} .\right]$

  (b) Prove that the action of $[(z-a) /(z-b)]^{\delta}$ on $(\dagger)$ results in the exponential shifting,

  $$P\left\{\begin{array}{cccc} a & b & c \\ \alpha+\delta & \beta-\delta & \gamma & z \\ \alpha^{\prime}+\delta & \beta^{\prime}-\delta & \gamma^{\prime} \end{array}\right\}$$

  [Hint: It may prove useful to start by considering the relationship between two solutions, $\omega$ and $\omega_{1}$, which satisfy the $P$-equations described by the respective $P$-symbols ( $\dagger$ ) and ( $)$-]

  (c) Explain what is meant by a Möbius transformation of a second order differential equation. By using suitable transformations acting on $(\dagger)$, show how to obtain the $P$ symbol

  $$P\left\{\begin{array}{cccc} 0 & 1 & \infty \\ 0 & 0 & a & z \\ 1-c & c-a-b & b \end{array}\right\}$$

  which corresponds to the hypergeometric equation.

  (d) The hypergeometric function $F(a, b, c ; z)$ is defined to be the solution of the differential equation corresponding to $(\star)$ that is analytic at $z=0$ with $F(a, b, c ; 0)=1$, which corresponds to the exponent zero. Use exponential shifting to show that the second solution, which corresponds to the exponent $1-c$, is

  $$z^{1-c} F(a-c+1, b-c+1,2-c ; z) .$$

  comment

• Paper 1, Section II, 18F

  Galois Theory

  Part II, 2019

  (a) Suppose $K, L$ are fields and $\sigma_{1}, \ldots, \sigma_{m}$ are distinct embeddings of $K$ into $L$. Prove that there do not exist elements $\lambda_{1}, \ldots, \lambda_{m}$ of $L$ (not all zero) such that

  $$\lambda_{1} \sigma_{1}(x)+\cdots+\lambda_{m} \sigma_{m}(x)=0 \quad \text { for all } x \in K$$

  (b) For a finite field extension $K$ of a field $k$ and for $\sigma_{1}, \ldots, \sigma_{m}$ distinct $k$ automorphisms of $K$, show that $m \leqslant[K: k]$. In particular, if $G$ is a finite group of field automorphisms of a field $K$ with $K^{G}$ the fixed field, deduce that $|G| \leqslant\left[K: K^{G}\right]$.

  (c) If $K=\mathbb{Q}(x, y)$ with $x, y$ independent transcendentals over $\mathbb{Q}$, consider the group $G$ generated by automorphisms $\sigma$ and $\tau$ of $K$, where

  $$\sigma(x)=y, \sigma(y)=-x \quad \text { and } \quad \tau(x)=x, \tau(y)=-y .$$

  Prove that $|G|=8$ and that $K^{G}=\mathbb{Q}\left(x^{2}+y^{2}, x^{2} y^{2}\right)$.

  comment

• Paper 2, Section II, F

  Galois Theory

  Part II, 2019

  For any prime $p \neq 5$, explain briefly why the Galois group of $X^{5}-1$ over $\mathbb{F}_{p}$ is cyclic of order $d$, where $d=1$ if $p \equiv 1 \bmod 5, d=4$ if $p \equiv 2,3 \bmod 5$, and $d=2$ if $p \equiv 4$ $\bmod 5 .$

  Show that the splitting field of $X^{5}-5$ over $\mathbb{Q}$ is an extension of degree 20 .

  For any prime $p \neq 5$, prove that $X^{5}-5 \in \mathbb{F}_{p}[X]$ does not have an irreducible cubic as a factor. For $p \equiv 2$ or $3 \bmod 5$, show that $X^{5}-5$ is the product of a linear factor and an irreducible quartic over $\mathbb{F}_{p}$. For $p \equiv 1 \bmod 5$, show that either $X^{5}-5$ is irreducible over $\mathbb{F}_{p}$ or it splits completely.

  [You may assume the reduction mod p criterion for finding cycle types in the Galois group of a monic polynomial over $\mathbb{Z}$ and standard facts about finite fields.]

  comment

• Paper 3, Section II, F

  Galois Theory

  Part II, 2019

  Let $k$ be a field. For $m$ a positive integer, consider $X^{m}-1 \in k[X]$, where either char $k=0$, or char $k=p$ with $p$ not dividing $m$; explain why the polynomial has distinct roots in a splitting field.

  For $m$ a positive integer, define the $m$ th cyclotomic polynomial $\Phi_{m} \in \mathbb{C}[X]$ and show that it is a monic polynomial in $\mathbb{Z}[X]$. Prove that $\Phi_{m}$ is irreducible over $\mathbb{Q}$ for all $m$. [Hint: If $\Phi_{m}=f g$, with $f, g \in \mathbb{Z}[X]$ and $f$ monic irreducible with $0<\operatorname{deg} f<\operatorname{deg} \Phi_{m}$, and $\varepsilon$ is a root of $f$, show first that $\varepsilon^{p}$ is a root of $f$ for any prime $p$ not dividing $m$.]

  Let $F=X^{8}+X^{7}-X^{5}-X^{4}-X^{3}+X+1 \in \mathbb{Z}[X]$; by considering the product $\left(X^{2}-X+1\right) F$, or otherwise, show that $F$ is irreducible over $\mathbb{Q}$.

  comment

• Paper 4, Section II, $18 \mathrm{~F}$

  Galois Theory

  Part II, 2019

  State (without proof) a result concerning uniqueness of splitting fields of a polynomial.

  Given a polynomial $f \in \mathbb{Q}[X]$ with distinct roots, what is meant by its Galois group $\operatorname{Gal}_{\mathbb{Q}}(f)$ ? Show that $f$ is irreducible over $\mathbb{Q}$ if and only if $\mathrm{Gal}_{\mathbb{Q}}(f)$ acts transitively on the roots of $f$.

  Now consider an irreducible quartic of the form $g(X)=X^{4}+b X^{2}+c \in \mathbb{Q}[X]$. If $\alpha \in \mathbb{C}$ denotes a root of $g$, show that the splitting field $K \subset \mathbb{C}$ is $\mathbb{Q}(\alpha, \sqrt{c})$. Give an explicit description of $\operatorname{Gal}(K / \mathbb{Q})$ in the cases:

  (i) $\sqrt{c} \in \mathbb{Q}(\alpha)$, and

  (ii) $\sqrt{c} \notin \mathbb{Q}(\alpha)$.

  If $c$ is a square in $\mathbb{Q}$, deduce that $\operatorname{Gal}_{\mathbb{Q}}(g) \cong C_{2} \times C_{2}$. Conversely, if Gal $_{\mathbb{Q}}(g) \cong$ $C_{2} \times C_{2}$, show that $\sqrt{c}$ is invariant under at least two elements of order two in the Galois group, and deduce that $c$ is a square in $\mathbb{Q}$.

  comment

• Paper 4, Section II, D

  General Relativity

  Part II, 2019

  (a) Consider the spherically symmetric spacetime metric

  $$d s^{2}=-\lambda^{2} d t^{2}+\mu^{2} d r^{2}+r^{2} d \theta^{2}+r^{2} \sin ^{2} \theta d \phi^{2},$$

  where $\lambda$ and $\mu$ are functions of $t$ and $r$. Use the Euler-Lagrange equations for the geodesics of the spacetime to compute all non-vanishing Christoffel symbols for this metric.

  (b) Consider the static limit of the line element $(\dagger)$ where $\lambda$ and $\mu$ are functions of the radius $r$ only, and let the matter coupled to gravity be a spherically symmetric fluid with energy momentum tensor

  $$T^{\mu \nu}=(\rho+P) u^{\mu} u^{\nu}+P g^{\mu \nu}, \quad u^{\mu}=\left[\lambda^{-1}, 0,0,0\right]$$

  where the pressure $P$ and energy density $\rho$ are also functions of the radius $r$. For these Tolman-Oppenheimer-Volkoff stellar models, the Einstein and matter equations $G_{\mu \nu}=8 \pi T_{\mu \nu}$ and $\nabla_{\mu} T_{\nu}^{\mu}=0$ reduce to

  $$\begin{aligned} \frac{\partial_{r} \lambda}{\lambda} &=\frac{\mu^{2}-1}{2 r}+4 \pi r \mu^{2} P \\ \partial_{r} m &=4 \pi r^{2} \rho, \quad \text { where } \quad m(r)=\frac{r}{2}\left(1-\frac{1}{\mu^{2}}\right) \\ \partial_{r} P &=-(\rho+P)\left(\frac{\mu^{2}-1}{2 r}+4 \pi r \mu^{2} P\right) \end{aligned}$$

  Consider now a constant density solution to the above Einstein and matter equations, where $\rho$ takes the non-zero constant value $\rho_{0}$ out to a radius $R$ and $\rho=0$ for $r>R$. Show that for such a star,

  $$\partial_{r} P=\frac{4 \pi r}{1-\frac{8}{3} \pi \rho_{0} r^{2}}\left(P+\frac{1}{3} \rho_{0}\right)\left(P+\rho_{0}\right)$$

  and that the pressure at the centre of the star is

  $$P(0)=-\rho_{0} \frac{1-\sqrt{1-2 M / R}}{3 \sqrt{1-2 M / R}-1}, \quad \text { with } \quad M=\frac{4}{3} \pi \rho_{0} R^{3}$$

  Show that $P(0)$ diverges if $M=4 R / 9 . \quad$ [Hint: at the surface of the star the pressure vanishes: $P(R)=0 .]$

  comment

• Paper 2, Section II, D

  General Relativity

  Part II, 2019

  Consider the spacetime metric

  $$d s^{2}=-f(r) d t^{2}+\frac{1}{f(r)} d r^{2}+r^{2}\left(d \theta^{2}+\sin ^{2} \theta d \phi^{2}\right), \quad \text { with } \quad f(r)=1-\frac{2 m}{r}-H^{2} r^{2}$$

  where $H>0$ and $m>0$ are constants.

  (a) Write down the Lagrangian for geodesics in this spacetime, determine three independent constants of motion and show that geodesics obey the equation

  $$\dot{r}^{2}+V(r)=E^{2}$$

  where $E$ is constant, the overdot denotes differentiation with respect to an affine parameter and $V(r)$ is a potential function to be determined.

  (b) Sketch the potential $V(r)$ for the case of null geodesics, find any circular null geodesics of this spacetime, and determine whether they are stable or unstable.

  (c) Show that $f(r)$ has two positive roots $r_{-}$and $r_{+}$if $m H<1 / \sqrt{27}$ and that these satisfy the relation $r_{-}<1 /(\sqrt{3} H)<r_{+}$.

  (d) Describe in one sentence the physical significance of those points where $f(r)=0$.

  comment

• Paper 3, Section II, D

  General Relativity

  Part II, 2019

  (a) Let $\mathcal{M}$ be a manifold with coordinates $x^{\mu}$. The commutator of two vector fields $\boldsymbol{V}$ and $\boldsymbol{W}$ is defined as

  $$[\boldsymbol{V}, \boldsymbol{W}]^{\alpha}=V^{\nu} \partial_{\nu} W^{\alpha}-W^{\nu} \partial_{\nu} V^{\alpha}$$

  (i) Show that $[\boldsymbol{V}, \boldsymbol{W}]$ transforms like a vector field under a change of coordinates from $x^{\mu}$ to $\tilde{x}^{\mu}$.

  (ii) Show that the commutator of any two basis vectors vanishes, i.e.

  $$\left[\frac{\partial}{\partial x^{\alpha}}, \frac{\partial}{\partial x^{\beta}}\right]=0$$

  (iii) Show that if $\boldsymbol{V}$ and $\boldsymbol{W}$ are linear combinations (not necessarily with constant coefficients) of $n$ vector fields $\boldsymbol{Z}_{(a)}, a=1, \ldots, n$ that all commute with one another, then the commutator $[\boldsymbol{V}, \boldsymbol{W}]$ is a linear combination of the same $n$ fields $Z_{(a)}$.

  [You may use without proof the following relations which hold for any vector fields $\boldsymbol{V}_{1}, \boldsymbol{V}_{2}, \boldsymbol{V}_{3}$ and any function $f$ :

  $$\begin{aligned} {\left[\boldsymbol{V}_{1}, \boldsymbol{V}_{2}\right] } &=-\left[\boldsymbol{V}_{2}, \boldsymbol{V}_{1}\right] \\ {\left[\boldsymbol{V}_{1}, \boldsymbol{V}_{2}+\boldsymbol{V}_{3}\right] } &=\left[\boldsymbol{V}_{1}, \boldsymbol{V}_{2}\right]+\left[\boldsymbol{V}_{1}, \boldsymbol{V}_{3}\right] \\ {\left[\boldsymbol{V}_{1}, f \boldsymbol{V}_{2}\right] } &=f\left[\boldsymbol{V}_{1}, \boldsymbol{V}_{2}\right]+\boldsymbol{V}_{1}(f) \boldsymbol{V}_{2} \end{aligned}$$

  but you should clearly indicate each time relation $(1),(2)$, or (3) is used.]

  (b) Consider the 2-dimensional manifold $\mathbb{R}^{2}$ with Cartesian coordinates $\left(x^{1}, x^{2}\right)=$ $(x, y)$ carrying the Euclidean metric $g_{\alpha \beta}=\delta_{\alpha \beta}$.

  (i) Express the coordinate basis vectors $\partial_{r}$ and $\partial_{\theta}$, where $r$ and $\theta$ denote the usual polar coordinates, in terms of their Cartesian counterparts.

  (ii) Define the unit vectors

  $$\hat{\boldsymbol{r}}=\frac{\partial_{r}}{\left\|\partial_{r}\right\|}, \quad \hat{\boldsymbol{\theta}}=\frac{\partial_{\theta}}{\left\|\partial_{\theta}\right\|}$$

  and show that $(\hat{\boldsymbol{r}}, \hat{\boldsymbol{\theta}})$ are not a coordinate basis, i.e. there exist no coordinates $z^{\alpha}$ such that $\hat{\boldsymbol{r}}=\partial / \partial z^{1}$ and $\hat{\boldsymbol{\theta}}=\partial / \partial z^{2}$.

  comment

• Paper 1, Section II, D

  General Relativity

  Part II, 2019

  Let $(\mathcal{M}, \boldsymbol{g})$ be a spacetime and $\boldsymbol{\Gamma}$ the Levi-Civita connection of the metric $\boldsymbol{g}$. The Riemann tensor of this spacetime is given in terms of the connection by

  $$R_{\rho \alpha \beta}^{\gamma}=\partial_{\alpha} \Gamma_{\rho \beta}^{\gamma}-\partial_{\beta} \Gamma_{\rho \alpha}^{\gamma}+\Gamma_{\rho \beta}^{\mu} \Gamma_{\mu \alpha}^{\gamma}-\Gamma_{\rho \alpha}^{\mu} \Gamma_{\mu \beta}^{\gamma}$$

  The contracted Bianchi identities ensure that the Einstein tensor satisfies

  $$\nabla^{\mu} G_{\mu \nu}=0$$

  (a) Show that the Riemann tensor obeys the symmetry

  $$R_{\rho \alpha \beta}^{\mu}+R_{\beta \rho \alpha}^{\mu}+R_{\alpha \beta \rho}^{\mu}=0 .$$

  (b) Show that a vector field $V^{\alpha}$ satisfies the Ricci identity

  $$2 \nabla_{[\alpha} \nabla_{\beta]} V^{\gamma}=\nabla_{\alpha} \nabla_{\beta} V^{\gamma}-\nabla_{\beta} \nabla_{\alpha} V^{\gamma}=R_{\rho \alpha \beta}^{\gamma} V^{\rho}$$

  Calculate the analogous expression for a rank $\left(\begin{array}{l}2 \\ 0\end{array}\right)$ tensor $T^{\mu \nu}$, i.e. calculate $\nabla_{[\alpha} \nabla_{\beta]} T^{\mu \nu}$ in terms of the Riemann tensor.

  (c) Let $K^{\alpha}$ be a vector that satisfies the Killing equation

  $$\nabla_{\alpha} K_{\beta}+\nabla_{\beta} K_{\alpha}=0$$

  Use the symmetry relation of part (a) to show that

  $$\begin{gathered} \nabla_{\nu} \nabla_{\mu} K^{\alpha}=R_{\mu \nu \beta}^{\alpha} K^{\beta} \\ \nabla^{\mu} \nabla_{\mu} K^{\alpha}=-R_{\beta}^{\alpha} K^{\beta} \end{gathered}$$

  where $R_{\alpha \beta}$ is the Ricci tensor.

  (d) Show that

  $$K^{\alpha} \nabla_{\alpha} R=2 \nabla^{[\mu} \nabla^{\lambda]} \nabla_{[\mu} K_{\lambda]},$$

  and use the result of part (b) to show that the right hand side evaluates to zero, hence showing that $K^{\alpha} \nabla_{\alpha} R=0$.

  comment

• Paper 4, Section II, G

  Graph Theory

  Part II, 2019

  State and prove Hall's theorem.

  Let $n$ be an even positive integer. Let $X=\{A: A \subset[n]\}$ be the power set of $[n]=\{1,2, \ldots, n\}$. For $1 \leqslant i \leqslant n$, let $X_{i}=\{A \in X:|A|=i\}$. Let $Q$ be the graph with vertex set $X$ where $A, B \in X$ are adjacent if and only if $|A \triangle B|=1$. [Here, $A \triangle B$ denotes the symmetric difference of $A$ and $B$, given by $A \triangle B:=(A \cup B) \backslash(A \cap B) .]$

  Let $1 \leqslant i \leqslant \frac{n}{2}$. Why is the induced subgraph $Q\left[X_{i} \cup X_{i-1}\right]$ bipartite? Show that it contains a matching from $X_{i-1}$ to $X_{i}$.

  A chain in $X$ is a subset $\mathcal{C} \subset X$ such that whenever $A, B \in \mathcal{C}$ we have $A \subset B$ or $B \subset A$. What is the least positive integer $k$ such that $X$ can be partitioned into $k$ pairwise disjoint chains? Justify your answer.

  comment

• Paper 3, Section II, G

  Graph Theory

  Part II, 2019

  (a) What does it mean to say that a graph is bipartite?

  (b) Show that $G$ is bipartite if and only if it contains no cycles of odd length.

  (c) Show that if $G$ is bipartite then

  $$\frac{\operatorname{ex}(n ; G)}{\left(\begin{array}{l} n \\ 2 \end{array}\right)} \rightarrow 0$$

  as $n \rightarrow \infty$.

  [You may use without proof the Erdós-Stone theorem provided it is stated precisely.]

  (d) Let $G$ be a graph of order $n$ with $m$ edges. Let $U$ be a random subset of $V(G)$ containing each vertex of $G$ independently with probability $\frac{1}{2}$. Let $X$ be the number of edges with precisely one vertex in $U$. Find, with justification, $\mathbb{E}(X)$, and deduce that $G$ contains a bipartite subgraph with at least $\frac{m}{2}$ edges.

  By using another method of choosing a random subset of $V(G)$, or otherwise, show that if $n$ is even then $G$ contains a bipartite subgraph with at least $\frac{m n}{2(n-1)}$ edges.

  comment

• Paper 2, Section II, 17G

  Graph Theory

  Part II, 2019

  (a) Suppose that the edges of the complete graph $K_{6}$ are coloured blue and yellow. Show that it must contain a monochromatic triangle. Does this remain true if $K_{6}$ is replaced by $K_{5}$ ?

  (b) Let $t \geqslant 1$. Suppose that the edges of the complete graph $K_{3 t-1}$ are coloured blue and yellow. Show that it must contain $t$ edges of the same colour with no two sharing a vertex. Is there any $t \geqslant 1$ for which this remains true if $K_{3 t-1}$ is replaced by $K_{3 t-2}$ ?

  (c) Now let $t \geqslant 2$. Suppose that the edges of the complete graph $K_{n}$ are coloured blue and yellow in such a way that there are a blue triangle and a yellow triangle with no vertices in common. Show that there are also a blue triangle and a yellow triangle that do have a vertex in common. Hence, or otherwise, show that whenever the edges of the complete graph $K_{5 t}$ are coloured blue and yellow it must contain $t$ monochromatic triangles, all of the same colour, with no two sharing a vertex. Is there any $t \geqslant 2$ for which this remains true if $K_{5 t}$ is replaced by $K_{5 t-1}$ ? [You may assume that whenever the edges of the complete graph $K_{10}$ are coloured blue and yellow it must contain two monochromatic triangles of the same colour with no vertices in common.]

  comment

• Paper 1, Section II, 17G

  Graph Theory

  Part II, 2019

  Let $G$ be a connected $d$-regular graph.

  (a) Show that $d$ is an eigenvalue of $G$ with multiplicity 1 and eigenvector

  $$e=(11 \ldots 1)^{T}$$

  (b) Suppose that $G$ is strongly regular. Show that $G$ has at most three distinct eigenvalues.

  (c) Conversely, suppose that $G$ has precisely three distinct eigenvalues $d, \lambda$ and $\mu$. Let $A$ be the adjacency matrix of $G$ and let

  $$B=A^{2}-(\lambda+\mu) A+\lambda \mu I .$$

  Show that if $v$ is an eigenvector of $G$ that is not a scalar multiple of $e$ then $B v=0$. Deduce that $B$ is a scalar multiple of the matrix $J$ whose entries are all equal to one. Hence show that, for $i \neq j,\left(A^{2}\right)_{i j}$ depends only on whether or not vertices $i$ and $j$ are adjacent, and so $G$ is strongly regular.

  (d) Which connected $d$-regular graphs have precisely two eigenvalues? Justify your answer.

  comment

• Paper 3, Section II, C

  Integrable Systems

  Part II, 2019

  Suppose $\psi^{s}:(x, u) \mapsto(\tilde{x}, \tilde{u})$ is a smooth one-parameter group of transformations acting on $\mathbb{R}^{2}$, with infinitesimal generator

  $$V=\xi(x, u) \frac{\partial}{\partial x}+\eta(x, u) \frac{\partial}{\partial u}$$

  (a) Define the $n^{\text {th }}$ prolongation $\operatorname{Pr}^{(n)} V$ of $V$, and show that

  $$\operatorname{Pr}^{(n)} V=V+\sum_{i=1}^{n} \eta_{i} \frac{\partial}{\partial u^{(i)}}$$

  where you should give an explicit formula to determine the $\eta_{i}$ recursively in terms of $\xi$ and $\eta$.

  (b) Find the $n^{t h}$ prolongation of each of the following generators:

  $$V_{1}=\frac{\partial}{\partial x}, \quad V_{2}=x \frac{\partial}{\partial x}, \quad V_{3}=x^{2} \frac{\partial}{\partial x}$$

  (c) Given a smooth, real-valued, function $u=u(x)$, the Schwarzian derivative is defined by,

  $$S=S[u]:=\frac{u_{x} u_{x x x}-\frac{3}{2} u_{x x}^{2}}{u_{x}^{2}}$$

  Show that,

  $$\operatorname{Pr}^{(3)} V_{i}(S)=c_{i} S,$$

  for $i=1,2,3$ where $c_{i}$ are real functions which you should determine. What can you deduce about the symmetries of the equations: (i) $S[u]=0$, (ii) $S[u]=1$, (iii) $S[u]=\frac{1}{x^{2}}$ ?

  comment

• Paper 2, Section II, C

  Integrable Systems

  Part II, 2019

  Suppose $p=p(x)$ is a smooth, real-valued, function of $x \in \mathbb{R}$ which satisfies $p(x)>0$ for all $x$ and $p(x) \rightarrow 1, p_{x}(x), p_{x x}(x) \rightarrow 0$ as $|x| \rightarrow \infty$. Consider the Sturm-Liouville operator:

  $$L \psi:=-\frac{d}{d x}\left(p^{2} \frac{d \psi}{d x}\right)$$

  which acts on smooth, complex-valued, functions $\psi=\psi(x)$. You may assume that for any $k>0$ there exists a unique function $\varphi_{k}(x)$ which satisfies:

  $$L \varphi_{k}=k^{2} \varphi_{k}$$

  and has the asymptotic behaviour:

  $$\varphi_{k}(x) \sim \begin{cases}e^{-i k x} & \text { as } x \rightarrow-\infty \\ a(k) e^{-i k x}+b(k) e^{i k x} & \text { as } x \rightarrow+\infty\end{cases}$$

  (a) By analogy with the standard Schrödinger scattering problem, define the reflection and transmission coefficients: $R(k), T(k)$. Show that $|R(k)|^{2}+|T(k)|^{2}=1$. [Hint: You may wish to consider $W(x)=p(x)^{2}\left[\psi_{1}(x) \psi_{2}^{\prime}(x)-\psi_{2}(x) \psi_{1}^{\prime}(x)\right]$ for suitable functions $\psi_{1}$ and $\left.\psi_{2} \cdot\right]$

  (b) Show that, if $\kappa>0$, there exists no non-trivial normalizable solution $\psi$ to the equation

  $$L \psi=-\kappa^{2} \psi$$

  Assume now that $p=p(x, t)$, such that $p(x, t)>0$ and $p(x, t) \rightarrow 1, p_{x}(x, t), p_{x x}(x, t) \rightarrow$ 0 as $|x| \rightarrow \infty$. You are given that the operator $A$ defined by:

  $$A \psi:=-4 p^{3} \frac{d^{3} \psi}{d x^{3}}-18 p^{2} p_{x} \frac{d^{2} \psi}{d x^{2}}-\left(12 p p_{x}^{2}+6 p^{2} p_{x x}\right) \frac{d \psi}{d x}$$

  satisfies:

  $$(L A-A L) \psi=-\frac{d}{d x}\left(2 p^{4} p_{x x x} \frac{d \psi}{d x}\right)$$

  (c) Show that $L, A$ form a Lax pair if the Harry Dym equation,

  $$p_{t}=p^{3} p_{x x x}$$

  is satisfied. [You may assume $L=L^{\dagger}, A=-A^{\dagger}$.]

  (d) Assuming that $p$ solves the Harry Dym equation, find how the transmission and reflection amplitudes evolve as functions of $t$.

  comment

• Paper 1, Section II, C

  Integrable Systems

  Part II, 2019

  Let $M=\mathbb{R}^{2 n}=\left\{(\mathbf{q}, \mathbf{p}) \mid \mathbf{q}, \mathbf{p} \in \mathbb{R}^{n}\right\}$ be equipped with its standard Poisson bracket.

  (a) Given a Hamiltonian function $H=H(\mathbf{q}, \mathbf{p})$, write down Hamilton's equations for $(M, H)$. Define a first integral of the system and state what it means that the system is integrable.

  (b) Show that if $n=1$ then every Hamiltonian system is integrable whenever

  $$\left(\frac{\partial H}{\partial q}, \frac{\partial H}{\partial p}\right) \neq \mathbf{0}$$

  Let $\tilde{M}=\mathbb{R}^{2 m}=\left\{(\tilde{\mathbf{q}}, \tilde{\mathbf{p}}) \mid \tilde{\mathbf{q}}, \tilde{\mathbf{p}} \in \mathbb{R}^{m}\right\}$ be another phase space, equipped with its standard Poisson bracket. Suppose that $\tilde{H}=\tilde{H}(\tilde{\mathbf{q}}, \tilde{\mathbf{p}})$ is a Hamiltonian function for $\tilde{M}$. Define $\mathbf{Q}=\left(q_{1}, \ldots, q_{n}, \tilde{q}_{1}, \ldots, \tilde{q}_{m}\right), \mathbf{P}=\left(p_{1}, \ldots, p_{n}, \tilde{p}_{1}, \ldots, \tilde{p}_{m}\right)$ and let the combined phase space $\mathcal{M}=\mathbb{R}^{2(n+m)}=\{(\mathbf{Q}, \mathbf{P})\}$ be equipped with the standard Poisson bracket.

  (c) Show that if $(M, H)$ and $(\tilde{M}, \tilde{H})$ are both integrable, then so is $(\mathcal{M}, \mathcal{H})$, where the combined Hamiltonian is given by:

  $$\mathcal{H}(\mathbf{Q}, \mathbf{P})=H(\mathbf{q}, \mathbf{p})+\tilde{H}(\tilde{\mathbf{q}}, \tilde{\mathbf{p}})$$

  (d) Consider the $n$-dimensional simple harmonic oscillator with phase space $M$ and Hamiltonian $H$ given by:

  $$H=\frac{1}{2} p_{1}^{2}+\ldots+\frac{1}{2} p_{n}^{2}+\frac{1}{2} \omega_{1}^{2} q_{1}^{2}+\ldots+\frac{1}{2} \omega_{n}^{2} q_{n}^{2}$$

  where $\omega_{i}>0$. Using the results above, or otherwise, show that $(M, H)$ is integrable for $(\mathbf{q}, \mathbf{p}) \neq \mathbf{0}$.

  (e) Is it true that every bounded orbit of an integrable system is necessarily periodic? You should justify your answer.

  comment

• Paper 3, Section II, H

  Linear Analysis

  Part II, 2019

  (a) Let $X$ be a Banach space and consider the open unit ball $B=\{x \in X:\|x\|<1\}$. Let $T: X \rightarrow X$ be a bounded operator. Prove that $\overline{T(B)} \supset B \operatorname{implies} T(B) \supset B$.

  (b) Let $P$ be the vector space of all polynomials in one variable with real coefficients. Let $\|\cdot\|$ be any norm on $P$. Show that $(P,\|\cdot\|)$ is not complete.

  (c) Let $f: \mathbb{C} \rightarrow \mathbb{C}$ be entire, and assume that for every $z \in \mathbb{C}$ there is $n$ such that $f^{(n)}(z)=0$ where $f^{(n)}$ is the $n$-th derivative of $f$. Prove that $f$ is a polynomial.

  [You may use that an entire function vanishing on an open subset of $\mathbb{C}$ must vanish everywhere.]

  (d) A Banach space $X$ is said to be uniformly convex if for every $\varepsilon \in(0,2]$ there is $\delta>0$ such that for all $x, y \in X$ such that $\|x\|=\|y\|=1$ and $\|x-y\| \geqslant \varepsilon$, one has $\|(x+y) / 2\| \leqslant 1-\delta$. Prove that $\ell^{2}$ is uniformly convex.

  comment

• Paper 4, Section II, H

  Linear Analysis

  Part II, 2019

  (a) State and prove the Riesz representation theorem for a real Hilbert space $H$.

  [You may use that if $H$ is a real Hilbert space and $Y \subset H$ is a closed subspace, then $\left.H=Y \oplus Y_{.}^{\perp} .\right]$

  (b) Let $H$ be a real Hilbert space and $T: H \rightarrow H$ a bounded linear operator. Show that $T$ is invertible if and only if both $T$ and $T^{*}$ are bounded below. [Recall that an operator $S: H \rightarrow H$ is bounded below if there is $c>0$ such that $\|S x\| \geqslant c\|x\|$ for all $x \in H$.]

  (c) Consider the complex Hilbert space of two-sided sequences,

  $$X=\left\{\left(x_{n}\right)_{n \in \mathbb{Z}}: x_{n} \in \mathbb{C}, \sum_{n \in \mathbb{Z}}\left|x_{n}\right|^{2}<\infty\right\}$$

  with norm $\|x\|=\left(\sum_{n}\left|x_{n}\right|^{2}\right)^{1 / 2}$. Define $T: X \rightarrow X$ by $(T x)_{n}=x_{n+1}$. Show that $T$ is unitary and find the point spectrum and the approximate point spectrum of $T$.

  comment

• Paper 2, Section II, H

  Linear Analysis

  Part II, 2019

  (a) State the real version of the Stone-Weierstrass theorem and state the UrysohnTietze extension theorem.

  (b) In this part, you may assume that there is a sequence of polynomials $P_{i}$ such that $\sup _{x \in[0,1]}\left|P_{i}(x)-\sqrt{x}\right| \rightarrow 0$ as $i \rightarrow \infty$.

  Let $f:[0,1] \rightarrow \mathbb{R}$ be a continuous piecewise linear function which is linear on $[0,1 / 2]$ and on $[1 / 2,1]$. Using the polynomials $P_{i}$ mentioned above (but not assuming any form of the Stone-Weierstrass theorem), prove that there are polynomials $Q_{i}$ such that $\sup _{x \in[0,1]}\left|Q_{i}(x)-f(x)\right| \rightarrow 0$ as $i \rightarrow \infty$.

  (d) Which of the following families of functions are relatively compact in $C[0,1]$ with the supremum norm? Justify your answer.

  $$\begin{aligned} &\mathcal{F}_{1}=\left\{x \mapsto \frac{\sin (\pi n x)}{n}: n \in \mathbb{N}\right\} \\ &\mathcal{F}_{2}=\left\{x \mapsto \frac{\sin (\pi n x)}{n^{1 / 2}}: n \in \mathbb{N}\right\} \\ &\mathcal{F}_{3}=\{x \mapsto \sin (\pi n x): n \in \mathbb{N}\} \end{aligned}$$

  [In this question $\mathbb{N}$ denotes the set of positive integers.]

  comment

• Paper 1, Section II, H

  Linear Analysis

  Part II, 2019

  Let $F$ be the space of real-valued sequences with only finitely many nonzero terms.

  (a) For any $p \in[1, \infty)$, show that $F$ is dense in $\ell^{p}$. Is $F$ dense in $\ell^{\infty} ?$ Justify your answer.

  (b) Let $p \in[1, \infty)$, and let $T: F \rightarrow F$ be an operator that is bounded in the $\|\cdot\|_{p}$-norm, i.e., there exists a $C$ such that $\|T x\|_{p} \leqslant C\|x\|_{p}$ for all $x \in F$. Show that there is a unique bounded operator $\widetilde{T}: \ell^{p} \rightarrow \ell^{p}$ satisfying $\left.\widetilde{T}\right|_{F}=T$, and that $\|\widetilde{T}\|_{p} \leqslant C$.

  (c) For each $p \in[1, \infty]$ and for each $i=1, \ldots, 5$ determine if there is a bounded operator from $\ell^{p}$ to $\ell^{p}$ (in the $\|\cdot\|_{p}$ norm) whose restriction to $F$ is given by $T_{i}$ :

  $$\begin{gathered} \left(T_{1} x\right)_{n}=n x_{n}, \quad\left(T_{2} x\right)_{n}=n\left(x_{n}-x_{n+1}\right), \quad\left(T_{3} x\right)_{n}=\frac{x_{n}}{n}, \\ \left(T_{4} x\right)_{n}=\frac{x_{1}}{n^{1 / 2}}, \quad\left(T_{5} x\right)_{n}=\frac{\sum_{j=1}^{n} x_{j}}{2^{n}} \end{gathered}$$

  (d) Let $X$ be a normed vector space such that the closed unit ball $\overline{B_{1}(0)}$ is compact. Prove that $X$ is finite dimensional.

  comment

• Paper 4, Section II, I

  Logic and Set Theory

  Part II, 2019

  Define the cardinals $\aleph_{\alpha}$, and explain briefly why every infinite set has cardinality $\operatorname{an} \aleph_{\alpha} .$

  Show that if $\kappa$ is an infinite cardinal then $\kappa^{2}=\kappa$.

  Let $X_{1}, X_{2}, \ldots, X_{n}$ be infinite sets. Show that $X_{1} \cup X_{2} \cup \cdots \cup X_{n}$ must have the same cardinality as $X_{i}$ for some $i$.

  Let $X_{1}, X_{2}, \ldots$ be infinite sets, no two of the same cardinality. Is it possible that $X_{1} \cup X_{2} \cup \ldots$ has the same cardinality as some $X_{i}$ ? Justify your answer.

  comment

• Paper 3, Section II, I

  Logic and Set Theory

  Part II, 2019

  Define the von Neumann hierarchy of sets $V_{\alpha}$. Show that each $V_{\alpha}$ is transitive, and explain why $V_{\alpha} \subset V_{\beta}$ whenever $\alpha \leqslant \beta$. Prove that every set $x$ is a member of some $V_{\alpha}$.

  Which of the following are true and which are false? Give proofs or counterexamples as appropriate. [You may assume standard properties of rank.]

  (i) If the rank of a set $x$ is a (non-zero) limit then $x$ is infinite.

  (ii) If the rank of a set $x$ is countable then $x$ is countable.

  (iii) If every finite subset of a set $x$ has rank at most $\alpha$ then $x$ has rank at most $\alpha$.

  (iv) For every ordinal $\alpha$ there exists a set of $\operatorname{rank} \alpha$.

  comment

• Paper 2, Section II, I

  Logic and Set Theory

  Part II, 2019

  Give the inductive and synthetic definitions of ordinal addition, and prove that they are equivalent.

  Which of the following assertions about ordinals $\alpha, \beta$ and $\gamma$ are always true, and which can be false? Give proofs or counterexamples as appropriate.

  (i) $\alpha+(\beta+\gamma)=(\alpha+\beta)+\gamma$.

  (ii) If $\alpha$ and $\beta$ are uncountable then $\alpha+\beta=\beta+\alpha$.

  (iii) $\alpha(\beta \gamma)=(\alpha \beta) \gamma$.

  (iv) If $\alpha$ and $\beta$ are infinite and $\alpha+\beta=\beta+\alpha$ then $\alpha \beta=\beta \alpha$.

  comment

• Paper 1, Section II, I

  Logic and Set Theory

  Part II, 2019

  State the completeness theorem for propositional logic. Explain briefly how the proof of this theorem changes from the usual proof in the case when the set of primitive propositions may be uncountable.

  State the compactness theorem and the decidability theorem, and deduce them from the completeness theorem.

  A poset $(X,<)$ is called two-dimensional if there exist total orders $<_{1}$ and $<_{2}$ on $X$ such that $x<y$ if and only if $x<_{1} y$ and $x<_{2} y$. By applying the compactness theorem for propositional logic, show that if every finite subset of a poset is two-dimensional then so is the poset itself.

  [Hint: Take primitive propositions $p_{x, y}$ and $q_{x, y}$, for each distinct $x, y \in X$, with the intended interpretation that $p_{x, y}$ is true if and only if $x<_{1} y$ and $q_{x, y}$ is true if and only if $x<2 y .]$

  comment

• Paper 4, Section I, C

  Mathematical Biology

  Part II, 2019

  (a) A variant of the classic logistic population model is given by:

  $$\frac{d x(t)}{d t}=\alpha\left[x(t)-x(t-T)^{2}\right]$$

  where $\alpha, T>0$.

  Show that for small $T$, the constant solution $x(t)=1$ is stable.

  Allow $T$ to increase. Express in terms of $\alpha$ the value of $T$ at which the constant solution $x(t)=1$ loses stability.

  (b) Another variant of the logistic model is given by this equation:

  $$\frac{d x(t)}{d t}=\alpha x(t-T)[1-x(t)]$$

  where $\alpha, T>0$. When is the constant solution $x(t)=1$ stable for this model?

  comment

• Paper 3, Section I, $\mathbf{6 C}$

  Mathematical Biology

  Part II, 2019

  A model of wound healing in one spatial dimension is given by

  $$\frac{\partial S}{\partial t}=r S(1-S)+D \frac{\partial^{2} S}{\partial x^{2}}$$

  where $S(x, t)$ gives the density of healthy tissue at spatial position $x$ at time $t$ and $r$ and $D$ are positive constants.

  By setting $S(x, t)=f(\xi)$ where $\xi=x-c t$, seek a steady travelling wave solution where $f(\xi)$ tends to one for large negative $\xi$ and tends to zero for large positive $\xi$. By linearising around the leading edge, where $f \approx 1$, find the possible wave speeds $c$ of the system. Assuming that the full nonlinear system will settle to the slowest possible speed, express the wave speed as a function of $D$ and $r$.

  Consider now a situation where the tissue is destroyed in some window of length $W$, i.e. $S(x, 0)=0$ for $0<x<W$ for some constant $W>0$ and $S(x, 0)$ is equal to one elsewhere. Explain what will happen for subsequent times, illustrating your answer with sketches of $S(x, t)$. Determine approximately how long it will take for this wound to heal (in the sense that $S$ is close to one everywhere).

  comment

• Paper 2, Section I, C

  Mathematical Biology

  Part II, 2019

  An activator-inhibitor system for $u(x, t)$ and $v(x, t)$ is described by the equations

  $$\begin{aligned} \frac{\partial u}{\partial t} &=u v^{2}-a+D \frac{\partial^{2} u}{\partial x^{2}} \\ \frac{\partial v}{\partial t} &=v-u v^{2}+\frac{\partial^{2} v}{\partial x^{2}} \end{aligned}$$

  where $a, D>0$.

  Find the range of $a$ for which the spatially homogeneous system has a stable equilibrium solution with $u>0$ and $v>0$.

  For the case when the homogeneous system is stable, consider spatial perturbations proportional to $\cos (k x)$ to the equilibrium solution found above. Give a condition on $D$ in terms of $a$ for the system to have a Turing instability (a spatial instability).

  comment

• Paper 1, Section $I$, $\mathbf{6 C}$

  Mathematical Biology

  Part II, 2019

  An animal population has annual dynamics, breeding in the summer and hibernating through the winter. At year $t$, the number of individuals alive who were born a years ago is given by $n_{a, t}$. Each individual of age $a$ gives birth to $b_{a}$ offspring, and after the summer has a probability $\mu_{a}$ of dying during the winter. [You may assume that individuals do not give birth during the year in which they are born.]

  Explain carefully why the following equations, together with initial conditions, are appropriate to describe the system:

  $$\begin{aligned} n_{0, t} &=\sum_{a=1}^{\infty} n_{a, t} b_{a} \\ n_{a+1, t+1} &=\left(1-\mu_{a}\right) n_{a, t}, \end{aligned}$$

  Seek a solution of the form $n_{a, t}=r_{a} \gamma^{t}$ where $\gamma$ and $r_{a}$, for $a=1,2,3 \ldots$, are constants. Show $\gamma$ must satisfy $\phi(\gamma)=1$ where

  $$\phi(\gamma)=\sum_{a=1}^{\infty}\left(\prod_{i=0}^{a-1}\left(1-\mu_{i}\right)\right) \gamma^{-a} b_{a}$$

  Explain why, for any reasonable set of parameters $\mu_{i}$ and $b_{i}$, the equation $\phi(\gamma)=1$ has a unique solution. Explain also how $\phi(1)$ can be used to determine if the population will grow or shrink.

  comment

• Paper 3, Section II, C

  Mathematical Biology

  Part II, 2019

  (a) A stochastic birth-death process has a master equation given by

  $$\frac{d p_{n}}{d t}=\lambda\left(p_{n-1}-p_{n}\right)+\beta\left[(n+1) p_{n+1}-n p_{n}\right]$$

  where $p_{n}(t)$ is the probability that there are $n$ individuals in the population at time $t$ for $n=0,1,2, \ldots$ and $p_{n}=0$ for $n<0$.

  (i) Give a brief interpretation of $\lambda$ and $\beta$.

  (ii) Derive an equation for $\frac{\partial \phi}{\partial t}$, where $\phi$ is the generating function

  $$\phi(s, t)=\sum_{n=0}^{\infty} s^{n} p_{n}(t)$$

  (iii) Assuming that the generating function $\phi$ takes the form

  $$\phi(s, t)=e^{(s-1) f(t)}$$

  find $f(t)$ and hence show that, as $t \rightarrow \infty$, both the mean $\langle n\rangle$ and variance $\sigma^{2}$ of the population size tend to constant values, which you should determine.

  (b) Now suppose an extra process is included: $k$ individuals are added to the population at rate $\epsilon(n)$.

  (i) Write down the new master equation, and explain why, for $k>1$, the approach used in part (a) will fail.

  (ii) By working with the master equation directly, find a differential equation for the rate of change of the mean population size $\langle n\rangle$.

  (iii) Now take $\epsilon(n)=a n+b$ for positive constants $a$ and $b$. Show that for $\beta>a k$ the mean population size tends to a constant, which you should determine. Briefly describe what happens for $\beta<a k$.

  comment

• Paper 4, Section II, C

  Mathematical Biology

  Part II, 2019

  A model of an infectious disease in a plant population is given by

  $$\begin{aligned} \dot{S} &=(S+I)-(S+I) S-\beta I S \\ \dot{I} &=-(S+I) I+\beta I S \end{aligned}$$

  where $S(t)$ is the density of healthy plants and $I(t)$ is the density of diseased plants at time $t$ and $\beta$ is a positive constant.

  (a) Give an interpretation of what each of the terms in equations (1) and (2) represents in terms of the dynamics of the plants. What does the coefficient $\beta$ represent? What can you deduce from the equations about the effect of the disease on the plants?

  (b) By finding all fixed points for $S \geqslant 0$ and $I \geqslant 0$ and analysing their stability, explain what will happen to a healthy plant population if the disease is introduced. Sketch the phase diagram, treating the cases $\beta<1$ and $\beta>1$ separately.

  (c) Define new variables $N(t)$ for the total plant population density and $\theta(t)$ for the proportion of the population that is diseased. Starting from equations (1) and (2) above, derive equations for $\dot{N}$ and $\dot{\theta}$ purely in terms of $N, \theta$ and $\beta$. Without carrying out a full fixed point analysis, explain how this system can be used directly to show the same results you had in part (b). [Hint: start by considering the dynamics of $N(t)$ alone.]

  (d) Suppose now that in an attempt to control disease, plants are culled at a rate $k$ per capita, independently of whether the plants are healthy or diseased. Write down the modified versions of equations (1) and (2). Use these to build updated equations for $\dot{N}$ and $\dot{\theta}$. Without carrying out a detailed fixed point analysis, what can you deduce about the effect of culling? Give the range of $k$ for which culling can effectively control the disease.

  comment

• Paper 4, Section II, 20G

  Number Fields

  Part II, 2019

  (a) Let $L$ be a number field, and suppose there exists $\alpha \in \mathcal{O}_{L}$ such that $\mathcal{O}_{L}=\mathbb{Z}[\alpha]$. Let $f(X) \in \mathbb{Z}[X]$ denote the minimal polynomial of $\alpha$, and let $p$ be a prime. Let $\bar{f}(X) \in(\mathbb{Z} / p \mathbb{Z})[X]$ denote the reduction modulo $p$ of $f(X)$, and let

  $$\bar{f}(X)=\bar{g}_{1}(X)^{e_{1}} \cdots \bar{g}_{r}(X)^{e_{r}}$$

  denote the factorisation of $\bar{f}(X)$ in $(\mathbb{Z} / p \mathbb{Z})[X]$ as a product of powers of distinct monic irreducible polynomials $\bar{g}_{1}(X), \ldots, \bar{g}_{r}(X)$, where $e_{1}, \ldots, e_{r}$ are all positive integers.

  For each $i=1, \ldots, r$, let $g_{i}(X) \in \mathbb{Z}[X]$ be any polynomial with reduction modulo $p$ equal to $\bar{g}_{i}(X)$, and let $P_{i}=\left(p, g_{i}(\alpha)\right) \subset \mathcal{O}_{L}$. Show that $P_{1}, \ldots, P_{r}$ are distinct, non-zero prime ideals of $\mathcal{O}_{L}$, and that there is a factorisation

  $$p \mathcal{O}_{L}=P_{1}^{e_{1}} \cdots P_{r}^{e_{r}}$$

  and that $N\left(P_{i}\right)=p^{\operatorname{deg} \bar{g}_{i}(X)}$.

  (b) Let $K$ be a number field of degree $n=[K: \mathbb{Q}]$, and let $p$ be a prime. Suppose that there is a factorisation

  $$p \mathcal{O}_{K}=Q_{1} \cdots Q_{s}$$

  where $Q_{1}, \ldots, Q_{s}$ are distinct, non-zero prime ideals of $\mathcal{O}_{K}$ with $N\left(Q_{i}\right)=p$ for each $i=$ $1, \ldots, s$. Use the result of part (a) to show that if $n>p$ then there is no $\alpha \in \mathcal{O}_{K}$ such that $\mathcal{O}_{K}=\mathbb{Z}[\alpha]$.

  comment

• Paper 2, Section II, G

  Number Fields

  Part II, 2019

  (a) Let $L$ be a number field. State Minkowski's upper bound for the norm of a representative for a given class of the ideal class group $\mathrm{Cl}\left(\mathcal{O}_{L}\right)$.

  (b) Now let $K=\mathbb{Q}(\sqrt{-47})$ and $\omega=\frac{1}{2}(1+\sqrt{-47})$. Using Dedekind's criterion, or otherwise, factorise the ideals $(\omega)$ and $(2+\omega)$ as products of non-zero prime ideals of $\mathcal{O}_{K}$.

  (c) Show that $\mathrm{Cl}\left(\mathcal{O}_{K}\right)$ is cyclic, and determine its order.

  [You may assume that $\left.\mathcal{O}_{K}=\mathbb{Z}[\omega] .\right]$

  comment

• Paper 1, Section II, 20G

  Number Fields

  Part II, 2019

  Let $K=\mathbb{Q}(\sqrt{2})$.

  (a) Write down the ring of integers $\mathcal{O}_{K}$.

  (b) State Dirichlet's unit theorem, and use it to determine all elements of the group of units $\mathcal{O}_{K}^{\times}$.

  (c) Let $P \subset \mathcal{O}_{K}$ denote the ideal generated by $3+\sqrt{2}$. Show that the group

  $$G=\left\{\alpha \in \mathcal{O}_{K}^{\times} \mid \alpha \equiv 1 \bmod P\right\}$$

  is cyclic, and find a generator.

  comment

• Paper 4, Section I, I

  Number Theory

  Part II, 2019

  Show that the product

  $$\prod_{p \text { prime }}\left(1-\frac{1}{p}\right)^{-1}$$

  and the series

  $$\sum_{p \text { prime }} \frac{1}{p}$$

  are both divergent.

  comment

• Paper 3, Section I, I

  Number Theory

  Part II, 2019

  Let $f=(a, b, c)$ be a positive definite binary quadratic form with integer coefficients. What does it mean to say that $f$ is reduced? Show that if $f$ is reduced and has discriminant $d$, then $|b| \leqslant a \leqslant \sqrt{|d| / 3}$ and $b \equiv d(\bmod 2)$. Deduce that for fixed $d<0$, there are only finitely many reduced $f$ of discriminant $d$.

  Find all reduced positive definite binary quadratic forms of discriminant $-15$.

  comment

• Paper 2, Section I, I

  Number Theory

  Part II, 2019

  Define the Jacobi symbol $\left(\frac{a}{n}\right)$, where $a, n \in \mathbb{Z}$ and $n$ is odd and positive.

  State and prove the Law of Quadratic Reciprocity for the Jacobi symbol. [You may use Quadratic Reciprocity for the Legendre symbol without proof but should state it clearly.]

  Compute the Jacobi symbol $\left(\frac{503}{2019}\right)$.

  comment

• Paper 1, Section I, I

  Number Theory

  Part II, 2019

  (a) State and prove the Chinese remainder theorem.

  (b) Let $N$ be an odd positive composite integer, and $b$ a positive integer with $(b, N)=1$. What does it mean to say that $N$ is a Fermat pseudoprime to base b? Show that 35 is a Fermat pseudoprime to base $b$ if and only if $b$ is congruent to one of $1,6,29$ or $34(\bmod 35)$.

  comment

• Paper 4, Section II, I

  Number Theory

  Part II, 2019

  (a) Let $a_{0}, a_{1}, \ldots$ be positive integers, and $\beta>0$ a positive real number. Show that for every $n \geqslant 0$, if $\theta_{n}=\left[a_{0}, \ldots, a_{n}, \beta\right]$, then $\theta_{n}=\left(\beta p_{n}+p_{n-1}\right) /\left(\beta q_{n}+q_{n-1}\right)$, where $\left(p_{n}\right)$, $\left(q_{n}\right)(n \geqslant-1)$ are sequences of integers satisfying

  $$\begin{aligned} &p_{0}=a_{0}, q_{0}=1, \quad p_{-1}=1, \quad q_{-1}=0 \quad \text { and } \\ &\left(\begin{array}{cc} p_{n} & p_{n-1} \\ q_{n} & q_{n-1} \end{array}\right)=\left(\begin{array}{cc} p_{n-1} & p_{n-2} \\ q_{n-1} & q_{n-2} \end{array}\right)\left(\begin{array}{cc} a_{n} & 1 \\ 1 & 0 \end{array}\right) \quad(n \geqslant 1) \end{aligned}$$

  Show that $p_{n} q_{n-1}-p_{n-1} q_{n}=(-1)^{n-1}$, and that $\theta_{n}$ lies between $p_{n} / q_{n}$ and $p_{n-1} / q_{n-1}$.

  (b) Show that if $\left[a_{0}, a_{1}, \ldots\right]$ is the continued fraction expansion of a positive irrational $\theta$, then $p_{n} / q_{n} \rightarrow \theta$ as $n \rightarrow \infty$.

  (c) Let the convergents of the continued fraction $\left[a_{0}, a_{1}, \ldots, a_{n}\right]$ be $p_{j} / q_{j}(0 \leqslant$ $j \leqslant n)$. Using part (a) or otherwise, show that the $n$-th and $(n-1)$-th convergents of $\left[a_{n}, a_{n-1}, \ldots, a_{0}\right]$ are $p_{n} / p_{n-1}$ and $q_{n} / q_{n-1}$ respectively.

  (d) Show that if $\theta=\left[\overline{a_{0}, a_{1}, \ldots, a_{n}}\right]$ is a purely periodic continued fraction with convergents $p_{j} / q_{j}$, then $f(\theta)=0$, where $f(X)=q_{n} X^{2}+\left(q_{n-1}-p_{n}\right) X-p_{n-1}$. Deduce that if $\theta^{\prime}$ is the other root of $f(X)$, then $-1 / \theta^{\prime}=\left[\overline{a_{n}, a_{n-1}, \ldots, a_{0}}\right]$.

  comment

• Paper 3, Section II, I

  Number Theory

  Part II, 2019

  Let $p>2$ be a prime.

  (a) What does it mean to say that an integer $g$ is a primitive root $\bmod p$ ?

  (b) Let $k$ be an integer with $0 \leqslant k<p-1$. Let

  $$S_{k}=\sum_{x=0}^{p-1} x^{k}$$

  Show that $S_{k} \equiv 0(\bmod p)$. [Recall that by convention $0^{0}=1$.]

  (c) Let $f(X, Y, Z)=a X^{2}+b Y^{2}+c Z^{2}$ for some $a, b, c \in \mathbb{Z}$, and let $g=1-f^{p-1}$. Show that for any $x, y, z \in \mathbb{Z}, g(x, y, z) \equiv 0$ or $1(\bmod p)$, and that

  $$\sum_{x, y, z \in\{0,1, \ldots, p-1\}} g(x, y, z) \equiv 0 \quad(\bmod p) .$$

  Hence show that there exist integers $x, y, z$, not all divisible by $p$, such that $f(x, y, z) \equiv 0$ $(\bmod p)$.

  comment

• Paper 4, Section II, C

  Numerical Analysis

  Part II, 2019

  For a 2-periodic analytic function $f$, its Fourier expansion is given by the formula

  $$f(x)=\sum_{n=-\infty}^{\infty} \widehat{f}_{n} e^{i \pi n x}, \quad \widehat{f}_{n}=\frac{1}{2} \int_{-1}^{1} f(t) e^{-i \pi n t} d t$$

  (a) Consider the two-point boundary value problem

  $$-\frac{1}{\pi^{2}}(1+2 \cos \pi x) u^{\prime \prime}+u=1+\sum_{n=1}^{\infty} \frac{2}{n^{2}+1} \cos \pi n x, \quad-1 \leqslant x \leqslant 1,$$

  with periodic boundary conditions $u(-1)=u(1)$. Construct explicitly the infinite dimensional linear algebraic system that arises from the application of the Fourier spectral method to the above equation, and explain how to truncate the system to a finitedimensional one.

  (b) A rectangle rule is applied to computing the integral of a 2-periodic analytic function $h$ :

  $$\int_{-1}^{1} h(t) d t \approx \frac{2}{N} \sum_{k=-N / 2+1}^{N / 2} h\left(\frac{2 k}{N}\right)$$

  Find an expression for the error $e_{N}(h):=\mathrm{LHS}-\mathrm{RHS}$ of $(*)$, in terms of $\widehat{h}_{n}$, and show that $e_{N}(h)$ has a spectral rate of decay as $N \rightarrow \infty$. [In the last part, you may quote a relevant theorem about $\widehat{h}_{n}$.]

  comment

• Paper 2, Section II, C

  Numerical Analysis

  Part II, 2019

  The Poisson equation on the unit square, equipped with zero boundary conditions, is discretized with the 9-point scheme:

  $$\begin{aligned} &-\frac{10}{3} u_{i, j}+\frac{2}{3}\left(u_{i+1, j}+u_{i-1, j}+u_{i, j+1}+u_{i, j-1}\right) \\ &+\frac{1}{6}\left(u_{i+1, j+1}+u_{i+1, j-1}+u_{i-1, j+1}+u_{i-1, j-1}\right)=h^{2} f_{i, j} \end{aligned}$$

  where $1 \leqslant i, j \leqslant m, u_{i, j} \approx u(i h, j h)$, and $(i h, j h)$ are the grid points with $h=\frac{1}{m+1}$. We also assume that $u_{0, j}=u_{i, 0}=u_{m+1, j}=u_{i, m+1}=0$.

  (a) Prove that all $m \times m$ tridiagonal symmetric Toeplitz (TST-) matrices

  $$H=[\beta, \alpha, \beta]:=\left[\begin{array}{cccc} \alpha & \beta & & \\ \beta & \alpha & \ddots & \\ & \ddots & \ddots & \beta \\ & & \beta & \alpha \end{array}\right] \in \mathbb{R}^{m \times m}$$

  share the same eigenvectors $\boldsymbol{q}_{k}$ with the components $(\sin j k \pi h)_{j=1}^{m}$ for $k=1, \ldots, m$. Find expressions for the corresponding eigenvalues $\lambda_{k}$ for $k=1, \ldots, m$. Deduce that $H=Q D Q^{-1}$, where $D=\operatorname{diag}\left\{\lambda_{k}\right\}$ and $Q$ is the matrix $(\sin i j \pi h)_{i, j=1}^{m} .$

  (b) Show that, by arranging the grid points ( $i h, j h)$ into a one-dimensional array by columns, the 9 -points scheme results in the following system of linear equations of the form

  $$A \boldsymbol{u}=\boldsymbol{b} \Leftrightarrow\left[\begin{array}{cccc} B & C & & \\ C & B & \ddots & \\ & \ddots & \ddots & C \\ & & C & B \end{array}\right]\left[\begin{array}{c} \boldsymbol{u}_{1} \\ \boldsymbol{u}_{2} \\ \vdots \\ \boldsymbol{u}_{m} \end{array}\right]=\left[\begin{array}{c} \boldsymbol{b}_{1} \\ \boldsymbol{b}_{2} \\ \vdots \\ \boldsymbol{b}_{m} \end{array}\right]$$

  where $A \in \mathbb{R}^{m^{2} \times m^{2}}$, the vectors $\boldsymbol{u}_{k}, \boldsymbol{b}_{k} \in \mathbb{R}^{m}$ are portions of $\boldsymbol{u}, \boldsymbol{b} \in \mathbb{R}^{m^{2}}$, respectively, and $B, C$ are $m \times m$ TST-matrices whose elements you should determine.

  (c) Using $\boldsymbol{v}_{k}=Q^{-1} \boldsymbol{u}_{k}, \boldsymbol{c}_{k}=Q^{-1} \boldsymbol{b}_{k}$, show that (2) is equivalent to

  $$\left[\begin{array}{cccc} D & E & & \\ E & D & \ddots & \\ & \ddots & \ddots & E \\ & & E & D \end{array}\right]\left[\begin{array}{c} \boldsymbol{v}_{1} \\ \boldsymbol{v}_{2} \\ \vdots \\ \boldsymbol{v}_{m} \end{array}\right]=\left[\begin{array}{c} \boldsymbol{c}_{1} \\ \boldsymbol{c}_{2} \\ \vdots \\ \boldsymbol{c}_{m} \end{array}\right]$$

  where $D$ and $E$ are diagonal matrices.

  (d) Show that, by appropriate reordering of the grid, the system (3) is reduced to $m$ uncoupled $m \times m$ systems of the form

  $$\Lambda_{k} \widehat{v}_{k}=\widehat{c}_{k}, \quad k=1, \ldots, m$$

  Determine the elements of the matrices $\Lambda_{k}$.

  comment

• Paper 3, Section II, 40C

  Numerical Analysis

  Part II, 2019

  The diffusion equation

  $$u_{t}=u_{x x}, \quad 0 \leqslant x \leqslant 1, \quad t \geqslant 0,$$

  with the initial condition $u(x, 0)=\phi(x), 0 \leqslant x \leqslant 1$, and boundary conditions $u(0, t)=$ $u(1, t)=0$, is discretised by $u_{m}^{n} \approx u(m h, n k)$ with $k=\Delta t, h=\Delta x=1 /(1+M)$. The Courant number is given by $\mu=k / h^{2}$.

  (a) The system is solved numerically by the method

  $$u_{m}^{n+1}=u_{m}^{n}+\mu\left(u_{m-1}^{n}-2 u_{m}^{n}+u_{m+1}^{n}\right), \quad m=1,2, \ldots, M, \quad n \geqslant 0 .$$

  Prove directly that $\mu \leqslant 1 / 2$ implies convergence.

  (b) Now consider the method

  $$a u_{m}^{n+1}-\frac{1}{4}(\mu-c)\left(u_{m-1}^{n+1}-2 u_{m}^{n+1}+u_{m+1}^{n+1}\right)=a u_{m}^{n}+\frac{1}{4}(\mu+c)\left(u_{m-1}^{n}-2 u_{m}^{n}+u_{m+1}^{n}\right)$$

  where $a$ and $c$ are real constants. Using an eigenvalue analysis and carefully justifying each step, determine conditions on $\mu, a$ and $c$ for this method to be stable.

  [You may use the notation $[\beta, \alpha, \beta]$ for the tridiagonal matrix with $\alpha$ along the diagonal, and $\beta$ along the sub-and super-diagonals and use without proof any relevant theorems about such matrices.]

  comment

• Paper 1, Section II, C

  Numerical Analysis

  Part II, 2019

  (a) Describe the Jacobi method for solving a system of linear equations $A \boldsymbol{x}=\boldsymbol{b}$ as a particular case of splitting, and state the criterion for its convergence in terms of the iteration matrix.

  (b) For the case when

  $$A=\left[\begin{array}{lll} 1 & \alpha & \alpha \\ \alpha & 1 & \alpha \\ \alpha & \alpha & 1 \end{array}\right]$$

  find the exact range of the parameter $\alpha$ for which the Jacobi method converges.

  (c) State the Householder-John theorem and deduce that the Jacobi method converges if $A$ is a symmetric positive-definite tridiagonal matrix.

  comment

• Paper 4, Section II, B

  Principles of Quantum Mechanics

  Part II, 2019

  Define the spin raising and spin lowering operators $S_{+}$and $S_{-}$. Show that

  $$S_{\pm}|s, \sigma\rangle=\hbar \sqrt{s(s+1)-\sigma(\sigma \pm 1)}|s, \sigma \pm 1\rangle,$$

  where $S_{z}|s, \sigma\rangle=\hbar \sigma|s, \sigma\rangle$ and $S^{2}|s, \sigma\rangle=s(s+1) \hbar^{2}|s, \sigma\rangle$.

  Two spin- $\frac{1}{2}$ particles, with spin operators $\mathbf{S}^{(1)}$ and $\mathbf{S}^{(2)}$, have a Hamiltonian

  $$H=\alpha \mathbf{S}^{(1)} \cdot \mathbf{S}^{(2)}+\mathbf{B} \cdot\left(\mathbf{S}^{(1)}-\mathbf{S}^{(2)}\right)$$

  where $\alpha$ and $\mathbf{B}=(0,0, B)$ are constants. Express $H$ in terms of the two particles' spin raising and spin lowering operators $S_{\pm}^{(1)}, S_{\pm}^{(2)}$ and the corresponding $z$-components $S_{z}^{(1)}$, $S_{z}^{(2)}$. Hence find the eigenvalues of $H$. Show that there is a unique groundstate in the limit $B \rightarrow 0$ and that the first excited state is triply degenerate in this limit. Explain this degeneracy by considering the action of the combined spin operator $\mathbf{S}^{(1)}+\mathbf{S}^{(2)}$ on the energy eigenstates.

  comment

• Paper 3, Section II, B

  Principles of Quantum Mechanics

  Part II, 2019

  Consider the Hamiltonian $H=H_{0}+V$, where $V$ is a small perturbation. If $H_{0}|n\rangle=E_{n}|n\rangle$, write down an expression for the eigenvalues of $H$, correct to second order in the perturbation, assuming the energy levels of $H_{0}$ are non-degenerate.

  In a certain three-state system, $H_{0}$ and $V$ take the form

  $$H_{0}=\left(\begin{array}{ccc} E_{1} & 0 & 0 \\ 0 & E_{2} & 0 \\ 0 & 0 & E_{3} \end{array}\right) \quad \text { and } \quad V=V_{0}\left(\begin{array}{ccc} 0 & \epsilon & \epsilon^{2} \\ \epsilon & 0 & 0 \\ \epsilon^{2} & 0 & 0 \end{array}\right)$$

  with $V_{0}$ and $\epsilon$ real, positive constants and $\epsilon \ll 1$.

  (a) Consider first the case $E_{1}=E_{2} \neq E_{3}$ and $\left|\epsilon V_{0} /\left(E_{3}-E_{2}\right)\right| \ll 1$. Use the results of degenerate perturbation theory to obtain the energy eigenvalues correct to order $\epsilon$.

  (b) Now consider the different case $E_{3}=E_{2} \neq E_{1}$ and $\left|\epsilon V_{0} /\left(E_{2}-E_{1}\right)\right| \ll 1$. Use the results of non-degenerate perturbation theory to obtain the energy eigenvalues correct to order $\epsilon^{2}$. Why is it not necessary to use degenerate perturbation theory in this case?

  (c) Obtain the exact energy eigenvalues in case (b), and compare these to your perturbative results by expanding to second order in $\epsilon$.

  comment

• Paper 2, Section II, B

  Principles of Quantum Mechanics

  Part II, 2019

  (a) Let $|i\rangle$ and $|j\rangle$ be two eigenstates of a time-independent Hamiltonian $H_{0}$, separated in energy by $\hbar \omega_{i j}$. At time $t=0$ the system is perturbed by a small, time independent operator $V$. The perturbation is turned off at time $t=T$. Show that if the system is initially in state $|i\rangle$, the probability of a transition to state $|j\rangle$ is approximately

  $$P_{i j}=4|\langle i|V| j\rangle|^{2} \frac{\sin ^{2}\left(\omega_{i j} T / 2\right)}{\left(\hbar \omega_{i j}\right)^{2}}$$

  (b) An uncharged particle with spin one-half and magnetic moment $\mu$ travels at speed $v$ through a region of uniform magnetic field $\mathbf{B}=(0,0, B)$. Over a length $L$ of its path, an additional perpendicular magnetic field $b$ is applied. The spin-dependent part of the Hamiltonian is

  $$H(t)= \begin{cases}-\mu\left(B \sigma_{z}+b \sigma_{x}\right) & \text { while } 0<t<L / v \\ -\mu B \sigma_{z} & \text { otherwise }\end{cases}$$

  where $\sigma_{z}$ and $\sigma_{x}$ are Pauli matrices. The particle initially has its spin aligned along the direction of $\mathbf{B}=(0,0, B)$. Find the probability that it makes a transition to the state with opposite spin

  (i) by assuming $b \ll B$ and using your result from part (a),

  (ii) by finding the exact evolution of the state.

  [Hint: for any 3-vector $\mathbf{a}, e^{i \mathbf{a} \cdot \boldsymbol{\sigma}}=(\cos a) I+(i \sin a) \hat{\mathbf{a}} \cdot \boldsymbol{\sigma}$, where $I$ is the $2 \times 2$ unit matrix, $\boldsymbol{\sigma}=\left(\sigma_{x}, \sigma_{y}, \sigma_{z}\right), \quad a=|\mathbf{a}|$ and $\left.\hat{\mathbf{a}}=\mathbf{a} /|\mathbf{a}| .\right]$

  comment

• Paper 1, Section II, B

  Principles of Quantum Mechanics

  Part II, 2019

  A $d=3$ isotropic harmonic oscillator of mass $\mu$ and frequency $\omega$ has lowering operators

  $$\mathbf{A}=\frac{1}{\sqrt{2 \mu \hbar \omega}}(\mu \omega \mathbf{X}+\mathrm{i} \mathbf{P})$$

  where $\mathbf{X}$ and $\mathbf{P}$ are the position and momentum operators. Assuming the standard commutation relations for $\mathbf{X}$ and $\mathbf{P}$, evaluate the commutators $\left[A_{i}^{\dagger}, A_{j}^{\dagger}\right],\left[A_{i}, A_{j}\right]$ and $\left[A_{i}, A_{j}^{\dagger}\right]$, for $i, j=1,2,3$, among the components of the raising and lowering operators.

  How is the ground state $|\mathbf{0}\rangle$ of the oscillator defined? How are normalised higher excited states obtained from $|\mathbf{0}\rangle$ ? [You should determine the appropriate normalisation constant for each energy eigenstate.]

  By expressing the orbital angular momentum operator $\mathbf{L}$ in terms of the raising and lowering operators, show that each first excited state of the isotropic oscillator has total orbital angular momentum quantum number $\ell=1$, and find a linear combination $|\psi\rangle$ of these first excited states obeying $L_{z}|\psi\rangle=+\hbar|\psi\rangle$ and $\||\psi\rangle \|=1$.

  comment

• Paper 4, Section II, J

  Principles of Statistics

  Part II, 2019

  We consider a statistical model $\{f(\cdot, \theta): \theta \in \Theta\}$.

  (a) Define the maximum likelihood estimator (MLE) and the Fisher information $I(\theta) .$

  (b) Let $\Theta=\mathbb{R}$ and assume there exist a continuous one-to-one function $\mu: \mathbb{R} \rightarrow \mathbb{R}$ and a real-valued function $h$ such that

  $$\mathbb{E}_{\theta}[h(X)]=\mu(\theta) \quad \forall \theta \in \mathbb{R}$$

  (i) For $X_{1}, \ldots, X_{n}$ i.i.d. from the model for some $\theta_{0} \in \mathbb{R}$, give the limit in almost sure sense of

  $$\hat{\mu}_{n}=\frac{1}{n} \sum_{i=1}^{n} h\left(X_{i}\right)$$

  Give a consistent estimator $\hat{\theta}_{n}$ of $\theta_{0}$ in terms of $\hat{\mu}_{n}$.

  (ii) Assume further that $\mathbb{E}_{\theta_{0}}\left[h(X)^{2}\right]<\infty$ and that $\mu$ is continuously differentiable and strictly monotone. What is the limit in distribution of $\sqrt{n}\left(\hat{\theta}_{n}-\theta_{0}\right)$. Assume too that the statistical model satisfies the usual regularity assumptions. Do you necessarily expect $\operatorname{Var}\left(\hat{\theta}_{n}\right) \geqslant\left(n I\left(\theta_{0}\right)\right)^{-1}$ for all $n$ ? Why?

  (iii) Propose an alternative estimator for $\theta_{0}$ with smaller bias than $\hat{\theta}_{n}$ if $B_{n}\left(\theta_{0}\right)=$ $\mathbb{E}_{\theta_{0}}\left[\hat{\theta}_{n}\right]-\theta_{0}=\frac{a}{n}+\frac{b}{n^{2}}+O\left(\frac{1}{n^{3}}\right)$ for some $a, b \in \mathbb{R}$ with $a \neq 0$.

  (iv) Further to all the assumptions in iii), assume that the MLE for $\theta_{0}$ is of the form

  $$\hat{\theta}_{M L E}=\frac{1}{n} \sum_{i=1}^{n} h\left(X_{i}\right)$$

  What is the link between the Fisher information at $\theta_{0}$ and the variance of $h(X)$ ? What does this mean in terms of the precision of the estimator and why?

  [You may use results from the course, provided you state them clearly.]

  comment

• Paper 3, Section II, J

  Principles of Statistics

  Part II, 2019

  We consider the exponential model $\{f(\cdot, \theta): \theta \in(0, \infty)\}$, where

  $$f(x, \theta)=\theta e^{-\theta x} \quad \text { for } x \geqslant 0$$

  We observe an i.i.d. sample $X_{1}, \ldots, X_{n}$ from the model.

  (a) Compute the maximum likelihood estimator $\hat{\theta}_{M L E}$ for $\theta$. What is the limit in distribution of $\sqrt{n}\left(\hat{\theta}_{M L E}-\theta\right)$ ?

  (b) Consider the Bayesian setting and place a $\operatorname{Gamma}(\alpha, \beta), \alpha, \beta>0$, prior for $\theta$ with density

  $$\pi(\theta)=\frac{\beta^{\alpha}}{\Gamma(\alpha)} \theta^{\alpha-1} \exp (-\beta \theta) \quad \text { for } \theta>0$$

  where $\Gamma$ is the Gamma function satisfying $\Gamma(\alpha+1)=\alpha \Gamma(\alpha)$ for all $\alpha>0$. What is the posterior distribution for $\theta$ ? What is the Bayes estimator $\hat{\theta}_{\pi}$ for the squared loss?

  (c) Show that the Bayes estimator is consistent. What is the limiting distribution of $\sqrt{n}\left(\hat{\theta}_{\pi}-\theta\right)$ ?

  [You may use results from the course, provided you state them clearly.]

  comment

• Paper 2, Section II, J

  Principles of Statistics

  Part II, 2019

  (a) We consider the model $\{\operatorname{Poisson}(\theta): \theta \in(0, \infty)\}$ and an i.i.d. sample $X_{1}, \ldots, X_{n}$ from it. Compute the expectation and variance of $X_{1}$ and check they are equal. Find the maximum likelihood estimator $\hat{\theta}_{M L E}$ for $\theta$ and, using its form, derive the limit in distribution of $\sqrt{n}\left(\hat{\theta}_{M L E}-\theta\right)$.

  (b) In practice, Poisson-looking data show overdispersion, i.e., the sample variance is larger than the sample expectation. For $\pi \in[0,1]$ and $\lambda \in(0, \infty)$, let $p_{\pi, \lambda}: \mathbb{N}_{0} \rightarrow[0,1]$,

  $$k \mapsto p_{\pi, \lambda}(k)= \begin{cases}\pi e^{-\lambda} \frac{\lambda^{k}}{k !} & \text { for } k \geqslant 1 \\ (1-\pi)+\pi e^{-\lambda} & \text { for } k=0\end{cases}$$

  Show that this defines a distribution. Does it model overdispersion? Justify your answer.

  (c) Let $Y_{1}, \ldots, Y_{n}$ be an i.i.d. sample from $p_{\pi, \lambda}$. Assume $\lambda$ is known. Find the maximum likelihood estimator $\hat{\pi}_{M L E}$ for $\pi$.

  (d) Furthermore, assume that, for any $\pi \in[0,1], \sqrt{n}\left(\hat{\pi}_{M L E}-\pi\right)$ converges in distribution to a random variable $Z$ as $n \rightarrow \infty$. Suppose we wanted to test the null hypothesis that our data arises from the model in part (a). Before making any further computations, can we necessarily expect $Z$ to follow a normal distribution under the null hypothesis? Explain. Check your answer by computing the appropriate distribution.

  [You may use results from the course, provided you state it clearly.]

  comment

• Paper 1, Section II, J

  Principles of Statistics

  Part II, 2019

  In a regression problem, for a given $X \in \mathbb{R}^{n \times p}$ fixed, we observe $Y \in \mathbb{R}^{n}$ such that

  $$Y=X \theta_{0}+\varepsilon$$

  for an unknown $\theta_{0} \in \mathbb{R}^{p}$ and $\varepsilon$ random such that $\varepsilon \sim \mathcal{N}\left(0, \sigma^{2} I_{n}\right)$ for some known $\sigma^{2}>0$.

  (a) When $p \leqslant n$ and $X$ has rank $p$, compute the maximum likelihood estimator $\hat{\theta}_{M L E}$ for $\theta_{0}$. When $p>n$, what issue is there with the likelihood maximisation approach and how many maximisers of the likelihood are there (if any)?

  (b) For any $\lambda>0$ fixed, we consider $\hat{\theta}_{\lambda}$ minimising

  $$\|Y-X \theta\|_{2}^{2}+\lambda\|\theta\|_{2}^{2}$$

  over $\mathbb{R}^{p}$. Derive an expression for $\hat{\theta}_{\lambda}$ and show it is well defined, i.e., there is a unique minimiser for every $X, Y$ and $\lambda$.

  Assume $p \leqslant n$ and that $X$ has rank $p$. Let $\Sigma=X^{\top} X$ and note that $\Sigma=V \Lambda V^{\top}$ for some orthogonal matrix $V$ and some diagonal matrix $\Lambda$ whose diagonal entries satisfy $\Lambda_{1,1} \geqslant \Lambda_{2,2} \geqslant \ldots \geqslant \Lambda_{p, p}$. Assume that the columns of $X$ have mean zero.

  (c) Denote the columns of $U=X V$ by $u_{1}, \ldots, u_{p}$. Show that they are sample principal components, i.e., that their pairwise sample correlations are zero and that they have sample variances $n^{-1} \Lambda_{1,1}, \ldots, n^{-1} \Lambda_{p, p}$, respectively. [Hint: the sample covariance between $u_{i}$ and $u_{j}$ is $n^{-1} u_{i}^{\top} u_{j}$.]

  (d) Show that

  $$\hat{Y}_{M L E}=X \hat{\theta}_{M L E}=U \Lambda^{-1} U^{\top} Y .$$

  Conclude that prediction $\hat{Y}_{M L E}$ is the closest point to $Y$ within the subspace spanned by the normalised sample principal components of part (c).

  (e) Show that

  $$\hat{Y}_{\lambda}=X \hat{\theta}_{\lambda}=U\left(\Lambda+\lambda I_{p}\right)^{-1} U^{\top} Y$$

  Assume $\Lambda_{1,1}, \Lambda_{2,2}, \ldots, \Lambda_{q, q}>>\lambda>>\Lambda_{q+1, q+1}, \ldots, \Lambda_{p, p}$ for some $1 \leqslant q<p$. Conclude that prediction $\hat{Y}_{\lambda}$ is approximately the closest point to $Y$ within the subspace spanned by the $q$ normalised sample principal components of part (c) with the greatest variance.

  comment

• Paper 2, Section II, K

  Probability and Measure

  Part II, 2019

  (a) Let $\left(X_{i}, \mathcal{A}_{i}\right)$ for $i=1,2$ be two measurable spaces. Define the product $\sigma$-algebra $\mathcal{A}_{1} \otimes \mathcal{A}_{2}$ on the Cartesian product $X_{1} \times X_{2}$. Given a probability measure $\mu_{i}$ on $\left(X_{i}, \mathcal{A}_{i}\right)$ for each $i=1,2$, define the product measure $\mu_{1} \otimes \mu_{2}$. Assuming the existence of a product measure, explain why it is unique. [You may use standard results from the course if clearly stated.]

  (b) Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space on which the real random variables $U$ and $V$ are defined. Explain what is meant when one says that $U$ has law $\mu$. On what measurable space is the measure $\mu$ defined? Explain what it means for $U$ and $V$ to be independent random variables.

  (c) Now let $X=\left[-\frac{1}{2}, \frac{1}{2}\right]$, let $\mathcal{A}$ be its Borel $\sigma$-algebra and let $\mu$ be Lebesgue measure. Give an example of a measure $\eta$ on the product $(X \times X, \mathcal{A} \otimes \mathcal{A})$ such that $\eta(X \times A)=\mu(A)=\eta(A \times X)$ for every Borel set $A$, but such that $\eta$ is not Lebesgue measure on $X \times X$.

  (d) Let $\eta$ be as in part (c) and let $I, J \subset X$ be intervals of length $x$ and $y$ respectively. Show that

  $$x+y-1 \leqslant \eta(I \times J) \leqslant \min \{x, y\}$$

  (e) Let $X$ be as in part (c). Fix $d \geqslant 2$ and let $\Pi_{i}$ denote the projection $\Pi_{i}\left(x_{1}, \ldots, x_{d}\right)=\left(x_{1}, \ldots, x_{i-1}, x_{i+1}, \ldots, x_{d}\right)$ from $X^{d}$ to $X^{d-1}$. Construct a probability measure $\eta$ on $X^{d}$, such that the image under each $\Pi_{i}$ coincides with the $(d-1)$-dimensional Lebesgue measure, while $\eta$ itself is not the $d$-dimensional Lebesgue measure. $[$ Hint: Consider the following collection of $2 d-1$ independent random variables: $U_{1}, \ldots, U_{d}$ uniformly distributed on $\left[0, \frac{1}{2}\right]$, and $\varepsilon_{1}, \ldots, \varepsilon_{d-1}$ such that $\mathbb{P}\left(\varepsilon_{i}=1\right)=\mathbb{P}\left(\varepsilon_{i}=-1\right)=\frac{1}{2}$ for each $i .]$

  comment

• Paper 3, Section II, K

  Probability and Measure

  Part II, 2019

  (a) Let $X$ and $Y$ be real random variables such that $\mathbb{E}[f(X)]=\mathbb{E}[f(Y)]$ for every compactly supported continuous function $f$. Show that $X$ and $Y$ have the same law.

  (b) Given a real random variable $Z$, let $\varphi_{Z}(s)=\mathbb{E}\left(e^{i s Z}\right)$ be its characteristic function. Prove the identity

  $$\iint g(\varepsilon s) f(x) e^{-i s x} \varphi_{Z}(s) d s d x=\int \hat{g}(t) \mathbb{E}[f(Z-\varepsilon t)] d t$$

  for real $\varepsilon>0$, where is $f$ is continuous and compactly supported, and where $g$ is a Lebesgue integrable function such that $\hat{g}$ is also Lebesgue integrable, where

  $$\hat{g}(t)=\int g(x) e^{i t x} d x$$

  is its Fourier transform. Use the above identity to derive a formula for $\mathbb{E}[f(Z)]$ in terms of $\varphi_{Z}$, and recover the fact that $\varphi_{Z}$ determines the law of $Z$ uniquely.

  (c) Let $X$ and $Y$ be bounded random variables such that $\mathbb{E}\left(X^{n}\right)=\mathbb{E}\left(Y^{n}\right)$ for every positive integer $n$. Show that $X$ and $Y$ have the same law.

  (d) The Laplace transform $\psi_{Z}(s)$ of a non-negative random variable $Z$ is defined by the formula

  $$\psi_{Z}(s)=\mathbb{E}\left(e^{-s Z}\right)$$

  for $s \geqslant 0$. Let $X$ and $Y$ be (possibly unbounded) non-negative random variables such that $\psi_{X}(s)=\psi_{Y}(s)$ for all $s \geqslant 0$. Show that $X$ and $Y$ have the same law.

  (e) Let

  $$f(x ; k)=1_{\{x>0\}} \frac{1}{k !} x^{k} e^{-x}$$

  where $k$ is a non-negative integer and $1_{\{x>0\}}$ is the indicator function of the interval $(0,+\infty)$.

  Given non-negative integers $k_{1}, \ldots, k_{n}$, suppose that the random variables $X_{1}, \ldots, X_{n}$ are independent with $X_{i}$ having density function $f\left(\cdot ; k_{i}\right)$. Find the density of the random variable $X_{1}+\cdots+X_{n}$.

  comment

• Paper 4, Section II, K

  Probability and Measure

  Part II, 2019

  (a) Let $\left(X_{n}\right)_{n \geqslant 1}$ and $X$ be real random variables with finite second moment on a probability space $(\Omega, \mathcal{F}, \mathbb{P})$. Assume that $X_{n}$ converges to $X$ almost surely. Show that the following assertions are equivalent:

  (i) $X_{n} \rightarrow X$ in $\mathbf{L}^{2}$ as $n \rightarrow \infty$

  (ii) $\mathbb{E}\left(X_{n}^{2}\right) \rightarrow \mathbb{E}\left(X^{2}\right)$ as $n \rightarrow \infty$.

  (b) Suppose now that $\Omega=(0,1), \mathcal{F}$ is the Borel $\sigma$-algebra of $(0,1)$ and $\mathbb{P}$ is Lebesgue measure. Given a Borel probability measure $\mu$ on $\mathbb{R}$ we set

  $$X_{\mu}(\omega)=\inf \left\{x \in \mathbb{R} \mid F_{\mu}(x) \geqslant \omega\right\}$$

  where $F_{\mu}(x):=\mu((-\infty, x])$ is the distribution function of $\mu$ and $\omega \in \Omega$.

  (i) Show that $X_{\mu}$ is a random variable on $(\Omega, \mathcal{F}, \mathbb{P})$ with law $\mu$.

  (ii) Let $\left(\mu_{n}\right)_{n \geqslant 1}$ and $\nu$ be Borel probability measures on $\mathbb{R}$ with finite second moments. Show that

  $$\mathbb{E}\left(\left(X_{\mu_{n}}-X_{\nu}\right)^{2}\right) \rightarrow 0 \text { as } n \rightarrow \infty$$

  if and only if $\mu_{n}$ converges weakly to $\nu$ and $\int x^{2} d \mu_{n}(x)$ converges to $\int x^{2} d \nu(x)$ as $n \rightarrow \infty$

  [You may use any theorem proven in lectures as long as it is clearly stated. Furthermore, you may use without proof the fact that $\mu_{n}$ converges weakly to $\nu$ as $n \rightarrow \infty$ if and only if $X_{\mu_{n}}$ converges to $X_{\nu}$ almost surely.]

  comment

• Paper 1, Section II, K

  Probability and Measure

  Part II, 2019

  Let $\mathbf{X}=\left(X_{1}, \ldots, X_{d}\right)$ be an $\mathbb{R}^{d}$-valued random variable. Given $u=\left(u_{1}, \ldots, u_{d}\right) \in$ $\mathbb{R}^{d}$ we let

  $$\phi_{\mathbf{X}}(u)=\mathbb{E}\left(e^{i\langle u, \mathbf{X}\rangle}\right)$$

  be its characteristic function, where $\langle\cdot, \cdot\rangle$ is the usual inner product on $\mathbb{R}^{d}$.

  (a) Suppose $\mathbf{X}$ is a Gaussian vector with mean 0 and covariance matrix $\sigma^{2} I_{d}$, where $\sigma>0$ and $I_{d}$ is the $d \times d$ identity matrix. What is the formula for the characteristic function $\phi_{\mathbf{X}}$ in the case $d=1$ ? Derive from it a formula for $\phi_{\mathbf{X}}$ in the case $d \geqslant 2$.

  (b) We now no longer assume that $\mathbf{X}$ is necessarily a Gaussian vector. Instead we assume that the $X_{i}$ 's are independent random variables and that the random vector $A \mathbf{X}$ has the same law as $\mathbf{X}$ for every orthogonal matrix $A$. Furthermore we assume that $d \geqslant 2$.

  (i) Show that there exists a continuous function $f:[0,+\infty) \rightarrow \mathbb{R}$ such that

  $$\phi_{\mathbf{X}}(u)=f\left(u_{1}^{2}+\ldots+u_{d}^{2}\right)$$

  [You may use the fact that for every two vectors $u, v \in \mathbb{R}^{d}$ such that $\langle u, u\rangle=\langle v, v\rangle$ there is an orthogonal matrix $A$ such that $A u=v$. ]

  (ii) Show that for all $r_{1}, r_{2} \geqslant 0$

  $$f\left(r_{1}+r_{2}\right)=f\left(r_{1}\right) f\left(r_{2}\right) .$$

  (iii) Deduce that $f$ takes values in $(0,1]$, and furthermore that there exists $\alpha \geqslant 0$ such that $f(r)=e^{-r \alpha}$, for all $r \geqslant 0$.

  (iv) What must be the law of $\mathbf{X}$ ?

  [Standard properties of characteristic functions from the course may be used without proof if clearly stated.]

  comment

• Paper 4, Section I, $10 D$

  Quantum Information and Computation

  Part II, 2019

  (a) Define the order of $\alpha \bmod N$ for coprime integers $\alpha$ and $N$ with $\alpha<N$. Explain briefly how knowledge of this order can be used to provide a factor of $N$, stating conditions on $\alpha$ and its order that must be satisfied.

  (b) Shor's algorithm for factoring $N$ starts by choosing $\alpha<N$ coprime. Describe the subsequent steps of a single run of Shor's algorithm that computes the order of $\alpha$ mod $N$ with probability $O(1 / \log \log N)$.

  [Any significant theorems that you invoke to justify the algorithm should be clearly stated (but proofs are not required). In addition you may use without proof the following two technical results.

  Theorem $F T$ : For positive integers $t$ and $M$ with $M \geqslant t^{2}$, and any $0 \leqslant x_{0}<t$, let $K$ be the largest integer such that $x_{0}+(K-1) t<M .$ Let QFT denote the quantum Fourier transform $\bmod M$. Suppose we measure $Q F T\left(\frac{1}{\sqrt{K}} \sum_{k=0}^{K-1}\left|x_{0}+k t\right\rangle\right)$ to obtain an integer $c$ with $0 \leqslant c<M .$ Then with probability $O(1 / \log \log t), c$ will be an integer closest to a multiple $j(M / t)$ of $M / t$ for which the value of $j$ (between 0 and $t$ ) is coprime to $t$.

  Theorem CF: For any rational number $a / b$ with $0<a / b<1$ and with integers a and $b$ having at most $n$ digits each, let $p / q$ with $p$ and $q$ coprime, be any rational number satisfying

  $$\left|\frac{a}{b}-\frac{p}{q}\right| \leqslant \frac{1}{2 q^{2}} .$$

  Then $p / q$ is one of the $O(n)$ convergents of the continued fraction of $a / b$ and all the convergents can be classically computed from $a / b$ in time $O\left(n^{3}\right)$.]

  comment

• Paper 3, Section I, $10 D$

  Quantum Information and Computation

  Part II, 2019

  Let $B_{n}$ denote the set of all $n$-bit strings and write $N=2^{n}$. Let $I$ denote the identity operator on $n$ qubits and for $G=\left\{x_{1}, x_{2}, \ldots, x_{k}\right\} \subset B_{n}$ introduce the $n$-qubit operator

  $$Q=-H_{n} I_{0} H_{n} I_{G}$$

  where $H_{n}=H \otimes \ldots \otimes H$ is the Hadamard operation on each of the $n$ qubits, and $I_{0}$ and $I_{G}$ are given by

  $$I_{0}=I-2|00 \ldots 0\rangle\left\langle 00 \ldots 0\left|\quad I_{G}=I-2 \sum_{x \in G}\right| x\right\rangle\langle x|$$

  Also introduce the states

  $$\left|\psi_{0}\right\rangle=\frac{1}{\sqrt{N}} \sum_{x \in B_{n}}|x\rangle \quad\left|\psi_{G}\right\rangle=\frac{1}{\sqrt{k}} \sum_{x \in G}|x\rangle \quad\left|\psi_{B}\right\rangle=\frac{1}{\sqrt{N-k}} \sum_{x \notin G}|x\rangle$$

  Let $\mathcal{P}$ denote the real span of $\left|\psi_{0}\right\rangle$ and $\left|\psi_{G}\right\rangle$.

  (a) Show that $Q$ maps $\mathcal{P}$ to itself, and derive a geometrical interpretation of the action of $Q$ on $\mathcal{P}$, stating clearly any results from Euclidean geometry that you use.

  (b) Let $f: B_{n} \rightarrow B_{1}$ be the Boolean function such that $f(x)=1$ iff $x \in G$. Suppose that $k=N / 4$. Show that we can obtain an $x \in G$ with certainty by using just one application of the standard quantum oracle $U_{f}$ for $f$ (together with other operations that are independent of $f$ ).

  comment

• Paper 2, Section I, $10 D$

  Quantum Information and Computation

  Part II, 2019

  The BB84 quantum key distribution protocol begins with Alice choosing two uniformly random bit strings $X=x_{1} x_{2} \ldots x_{m}$ and $Y=y_{1} y_{2} \ldots y_{m}$.

  (a) In terms of these strings, describe Alice's process of conjugate coding for the BB84 protocol.

  (b) Suppose Alice and Bob are distantly separated in space and have available a noiseless quantum channel on which there is no eavesdropping. They can also communicate classically publicly. For this idealised situation, describe the steps of the BB84 protocol that results in Alice and Bob sharing a secret key of expected length $m / 2$.

  (c) Suppose now that an eavesdropper Eve taps into the channel and carries out the following action on each passing qubit. With probability $1-p$, Eve lets it pass undisturbed, and with probability $p$ she chooses a bit $w \in\{0,1\}$ uniformly at random and measures the qubit in basis $B_{w}$ where $B_{0}=\{|0\rangle,|1\rangle\}$ and $B_{1}=\{(|0\rangle+|1\rangle) / \sqrt{2},(|0\rangle-|1\rangle) / \sqrt{2}\}$. After measurement Eve sends the post-measurement state on to Bob. Calculate the bit error rate for Alice and Bob's final key in part (b) that results from Eve's action.

  comment

• Paper 1, Section I, $10 D$ Introduce the 2 -qubit states

  Quantum Information and Computation

  Part II, 2019

  $$\left|\beta_{x z}\right\rangle=\left(Z^{z} X^{x}\right) \otimes I\left(\frac{|00\rangle+|11\rangle}{\sqrt{2}}\right)$$

  where $X$ and $Z$ are the standard qubit Pauli operations and $x, z \in\{0,1\}$.

  (a) For any 1-qubit state $|\alpha\rangle$ show that the 3 -qubit state $|\alpha\rangle_{C}\left|\beta_{00}\right\rangle_{A B}$ of system $C A B$ can be expressed as

  $$|\alpha\rangle_{C}\left|\beta_{00}\right\rangle_{A B}=\frac{1}{2} \sum_{x, z=0}^{1}\left|\beta_{x z}\right\rangle_{C A}\left|\mu_{x z}\right\rangle_{B}$$

  where the 1 -qubit states $\left|\mu_{x z}\right\rangle$ are uniquely determined. Show that $\left|\mu_{10}\right\rangle=X|\alpha\rangle$.

  (b) In addition to $\left|\mu_{10}\right\rangle=X|\alpha\rangle$ you may now assume that $\left|\mu_{x z}\right\rangle=X^{x} Z^{z}|\alpha\rangle$. Alice and Bob are separated distantly in space and share a $\left|\beta_{00}\right\rangle_{A B}$ state with $A$ and $B$ labelling qubits held by Alice and Bob respectively. Alice also has a qubit $C$ in state $|\alpha\rangle$ whose identity is unknown to her. Using the results of part (a) show how she can transfer the state of $C$ to Bob using only local operations and classical communication, i.e. the sending of quantum states across space is not allowed.

  (c) Suppose that in part (b), while sharing the $\left|\beta_{00}\right\rangle_{A B}$ state, Alice and Bob are also unable to engage in any classical communication, i.e. they are able only to perform local operations. Can Alice now, perhaps by a modified process, transfer the state of $C$ to Bob? Give a reason for your answer.

  comment

• Paper 3, Section II, D

  Quantum Information and Computation

  Part II, 2019

  Let $\mathcal{H}_{d}$ denote a $d$-dimensional state space with orthonormal basis $\left\{|y\rangle: y \in \mathbb{Z}_{d}\right\}$. For any $f: \mathbb{Z}_{m} \rightarrow \mathbb{Z}_{n}$ let $U_{f}$ be the operator on $\mathcal{H}_{m} \otimes \mathcal{H}_{n}$ defined by

  $$U_{f}|x\rangle|y\rangle=|x\rangle|y+f(x) \bmod n\rangle$$

  for all $x \in \mathbb{Z}_{m}$ and $y \in \mathbb{Z}_{n}$.

  (a) Define $Q F T$, the quantum Fourier transform $\bmod d$ (for any chosen $d)$.

  (b) Let $S$ on $\mathcal{H}_{d}$ (for any chosen $d$ ) denote the operator defined by

  $$S|y\rangle=|y+1 \bmod d\rangle$$

  for $y \in \mathbb{Z}_{d}$. Show that the Fourier basis states $\left|\xi_{x}\right\rangle=Q F T|x\rangle$ for $x \in \mathbb{Z}_{d}$ are eigenstates of $S$. By expressing $U_{f}$ in terms of $S$ find a basis of eigenstates of $U_{f}$ and determine the corresponding eigenvalues.

  (c) Consider the following oracle promise problem:

  Input: an oracle for a function $f: \mathbb{Z}_{3} \rightarrow \mathbb{Z}_{3}$.

  Promise: $f$ has the form $f(x)=s x+t$ where $s$ and $t$ are unknown coefficients (and with all arithmetic being $\bmod 3)$.

  Problem: Determine $s$ with certainty.

  Can this problem be solved by a single query to a classical oracle for $f$ (and possible further processing independent of $f)$ ? Give a reason for your answer.

  Using the results of part (b) or otherwise, give a quantum algorithm for this problem that makes just one query to the quantum oracle $U_{f}$ for $f$.

  (d) For any $f: \mathbb{Z}_{3} \rightarrow \mathbb{Z}_{3}$, let $f_{1}(x)=f(x+1)$ and $f_{2}(x)=-f(x)$ (all arithmetic being $\bmod 3$ ). Show how $U_{f_{1}}$ and $U_{f_{2}}$ can each be implemented with one use of $U_{f}$ together with other unitary gates that are independent of $f$.

  (e) Consider now the oracle problem of the form in part (c) except that now $f$ is a quadratic function $f(x)=a x^{2}+b x+c$ with unknown coefficients $a, b, c$ (and all arithmetic being mod 3), and the problem is to determine the coefficient $a$ with certainty. Using the results of part (d) or otherwise, give a quantum algorithm for this problem that makes just two queries to the quantum oracle for $f$.

  comment

• Paper 2, Section II, D

  Quantum Information and Computation

  Part II, 2019

  Let $\left|\alpha_{0}\right\rangle \neq\left|\alpha_{1}\right\rangle$ be two quantum states and let $p_{0}$ and $p_{1}$ be associated probabilities with $p_{0}+p_{1}=1, p_{0} \neq 0, p_{1} \neq 0$ and $p_{0} \geqslant p_{1}$. Alice chooses state $\left|\alpha_{i}\right\rangle$ with probability $p_{i}$ and sends it to Bob. Upon receiving it, Bob performs a 2-outcome measurement $\mathcal{M}$ with outcomes labelled 0 and 1 , in an attempt to identify which state Alice sent.

  (a) By using the extremal property of eigenvalues, or otherwise, show that the operator $D=p_{0}\left|\alpha_{0}\right\rangle\left\langle\alpha_{0}\left|-p_{1}\right| \alpha_{1}\right\rangle\left\langle\alpha_{1}\right|$ has exactly two nonzero eigenvalues, one of which is positive and the other negative.

  (b) Let $P_{S}$ denote the probability that Bob correctly identifies Alice's sent state. If the measurement $\mathcal{M}$ comprises orthogonal projectors $\left\{\Pi_{0}, \Pi_{1}\right\}$ (corresponding to outcomes 0 and 1 respectively) give an expression for $P_{S}$ in terms of $p_{1}, \Pi_{0}$ and $D$.

  (c) Show that the optimal success probability $P_{S}^{\text {opt }}$, i.e. the maximum attainable value of $P_{S}$, is

  $$P_{S}^{\mathrm{opt}}=\frac{1+\sqrt{1-4 p_{0} p_{1} \cos ^{2} \theta}}{2}$$

  where $\cos \theta=\left|\left\langle\alpha_{0} \mid \alpha_{1}\right\rangle\right|$.

  (d) Suppose we now place the following extra requirement on Bob's discrimination process: whenever Bob obtains output 0 then the state sent by Alice was definitely $\left|\alpha_{0}\right\rangle$. Show that Bob's $P_{S}^{\mathrm{opt}}$ now satisfies $P_{S}^{\mathrm{opt}} \geqslant 1-p_{0} \cos ^{2} \theta$.

  comment

• Paper 3, Section II, I

  Representation Theory

  Part II, 2019

  In this question all representations are complex and $G$ is a finite group.

  (a) State and prove Mackey's theorem. State the Frobenius reciprocity theorem.

  (b) Let $X$ be a finite $G$-set and let $\mathbb{C} X$ be the corresponding permutation representation. Pick any orbit of $G$ on $X$ : it is isomorphic as a $G$-set to $G / H$ for some subgroup $H$ of $G$. Write down the character of $\mathbb{C}(G / H)$.

  (i) Let $\mathbb{C}_{G}$ be the trivial representation of $G$. Show that $\mathbb{C} X$ may be written as a direct sum

  $$\mathbb{C} X=\mathbb{C}_{G} \oplus V$$

  for some representation $V$.

  (ii) Using the results of (a) compute the character inner product $\left\langle 1_{H} \uparrow^{G}, 1_{H} \uparrow^{G}\right\rangle_{G}$ in terms of the number of $(H, H)$ double cosets.

  (iii) Now suppose that $|X| \geqslant 2$, so that $V \neq 0$. By writing $\mathbb{C}(G / H)$ as a direct sum of irreducible representations, deduce from (ii) that the representation $V$ is irreducible if and only if $G$ acts 2 -transitively. In that case, show that $V$ is not the trivial representation.

  comment

• Paper 4, Section II, I

  Representation Theory

  Part II, 2019

  (a) What is meant by a compact topological group? Explain why $\mathrm{SU}(n)$ is an example of such a group.

  [In the following the existence of a Haar measure for any compact Hausdorff topological group may be assumed, if required.]

  (b) Let $G$ be any compact Hausdorff topological group. Show that there is a continuous group homomorphism $\rho: G \rightarrow \mathrm{O}(n)$ if and only if $G$ has an $n$-dimensional representation over $\mathbb{R}$. [Here $\mathrm{O}(n)$ denotes the subgroup of $\mathrm{GL}_{n}(\mathbb{R})$ preserving the standard (positive-definite) symmetric bilinear form.]

  (c) Explicitly construct such a representation $\rho: \mathrm{SU}(2) \rightarrow \mathrm{SO}(3)$ by showing that $\mathrm{SU}(2)$ acts on the following vector space of matrices,

  $$\left\{A=\left(\begin{array}{cc} a & b \\ c & -a \end{array}\right) \in \mathrm{M}_{2}(\mathbb{C}): A+\overline{A^{t}}=0\right\}$$

  by conjugation.

  Show that

  (i) this subspace is isomorphic to $\mathbb{R}^{3}$;

  (ii) the trace map $(A, B) \mapsto-\operatorname{tr}(A B)$ induces an invariant positive definite symmetric bilinear form;

  (iii) $\rho$ is surjective with kernel $\left\{\pm I_{2}\right\}$. [You may assume, without proof, that $\mathrm{SU}(2)$ is connected.]

  comment

• Paper 2, Section II, I

  Representation Theory

  Part II, 2019

  (a) For any finite group $G$, let $\rho_{1}, \ldots, \rho_{k}$ be a complete set of non-isomorphic complex irreducible representations of $G$, with dimensions $n_{1}, \ldots n_{k}$, respectively. Show that

  $$\sum_{j=1}^{k} n_{j}^{2}=|G|$$

  (b) Let $A, B, C, D$ be the matrices

  and let $G=\langle A, B, C, D\rangle$. Write $Z=-I_{4}$.

  (i) Prove that the derived subgroup $G^{\prime}=\langle Z\rangle$.

  (ii) Show that for all $g \in G, g^{2} \in\langle Z\rangle$, and deduce that $G$ is a 2-group of order at most 32 .

  (iii) Prove that the given representation of $G$ of degree 4 is irreducible.

  (iv) Prove that $G$ has order 32 , and find all the irreducible representations of $G$.

  $$\begin{aligned} & A=\left(\begin{array}{cccc}1 & 0 & 0 & 0 \\0 & -1 & 0 & 0 \\0 & 0 & 1 & 0 \\0 & 0 & 0 & -1\end{array}\right), \quad B=\left(\begin{array}{llll}0 & 1 & 0 & 0 \\1 & 0 & 0 & 0 \\0 & 0 & 0 & 1 \\0 & 0 & 1 & 0\end{array}\right) \\ & C=\left(\begin{array}{cccc}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 \\0 & 0 & -1 & 0 \\0 & 0 & 0 & -1\end{array}\right), \quad D=\left(\begin{array}{llll}0 & 0 & 1 & 0 \\0 & 0 & 0 & 1 \\1 & 0 & 0 & 0 \\0 & 1 & 0 & 0\end{array}\right) \end{aligned}$$

  comment

• Paper 1, Section II, I

  Representation Theory

  Part II, 2019

  (a) State and prove Schur's lemma over $\mathbb{C}$.

  In the remainder of this question we work over $\mathbb{R}$.

  (b) Let $G$ be the cyclic group of order 3 .

  (i) Write the regular $\mathbb{R} G$-module as a direct sum of irreducible submodules.

  (ii) Find all the intertwining homomorphisms between the irreducible $\mathbb{R} G$-modules. Deduce that the conclusion of Schur's lemma is false if we replace $\mathbb{C}$ by $\mathbb{R}$.

  (c) Henceforth let $G$ be a cyclic group of order $n$. Show that

  (i) if $n$ is even, the regular $\mathbb{R} G$-module is a direct sum of two (non-isomorphic) 1dimensional irreducible submodules and $(n-2) / 2$ (non-isomorphic) 2-dimensional irreducible submodules;

  (ii) if $n$ is odd, the regular $\mathbb{R} G$-module is a direct sum of one 1-dimensional irreducible submodule and $(n-1) / 2$ (non-isomorphic) 2-dimensional irreducible submodules.

  comment

• Paper 3, Section II, F

  Riemann Surfaces

  Part II, 2019

  Let $\Lambda$ be a lattice in $\mathbb{C}$, and $f: \mathbb{C} / \Lambda \rightarrow \mathbb{C} / \Lambda$ a holomorphic map of complex tori. Show that $f$ lifts to a linear map $F: \mathbb{C} \rightarrow \mathbb{C}$.

  Give the definition of $\wp(z):=\wp_{\Lambda}(z)$, the Weierstrass $\wp$-function for $\Lambda$. Show that there exist constants $g_{2}, g_{3}$ such that

  $$\wp^{\prime}(z)^{2}=4 \wp(z)^{3}-g_{2} \wp(z)-g_{3}$$

  Suppose $f \in \operatorname{Aut}(\mathbb{C} / \Lambda)$, that is, $f: \mathbb{C} / \Lambda \rightarrow \mathbb{C} / \Lambda$ is a biholomorphic group homomorphism. Prove that there exists a lift $F(z)=\zeta z$ of $f$, where $\zeta$ is a root of unity for which there exist $m, n \in \mathbb{Z}$ such that $\zeta^{2}+m \zeta+n=0$.

  comment

• Paper 2, Section II, F

  Riemann Surfaces

  Part II, 2019

  (a) Prove that $z \mapsto z^{4}$ as a map from the upper half-plane $\mathbb{H}$ to $\mathbb{C} \backslash\{0\}$ is a covering map which is not regular.

  (b) Determine the set of singular points on the unit circle for

  $$h(z)=\sum_{n=0}^{\infty}(-1)^{n}(2 n+1) z^{n}$$

  (c) Suppose $f: \Delta \backslash\{0\} \rightarrow \Delta \backslash\{0\}$ is a holomorphic map where $\Delta$ is the unit disk. Prove that $f$ extends to a holomorphic map $\tilde{f}: \Delta \rightarrow \Delta$. If additionally $f$ is biholomorphic, prove that $\tilde{f}(0)=0$.

  (d) Suppose that $g: \mathbb{C} \hookrightarrow R$ is a holomorphic injection with $R$ a compact Riemann surface. Prove that $R$ has genus 0 , stating carefully any theorems you use.

  comment

• Paper 1, Section II, F

  Riemann Surfaces

  Part II, 2019

  Define $X^{\prime}:=\left\{(x, y) \in \mathbb{C}^{2}: x^{3} y+y^{3}+x=0\right\}$.

  (a) Prove by defining an atlas that $X^{\prime}$ is a Riemann surface.

  (b) Now assume that by adding finitely many points, it is possible to compactify $X^{\prime}$ to a Riemann surface $X$ so that the coordinate projections extend to holomorphic maps $\pi_{x}$ and $\pi_{y}$ from $X$ to $\mathbb{C}_{\infty}$. Compute the genus of $X$.

  (c) Assume that any holomorphic automorphism of $X^{\prime}$ extends to a holomorphic automorphism of $X$. Prove that the group Aut $(\mathrm{X})$ of holomorphic automorphisms of $X$ contains an element $\phi$ of order 7 . Prove further that there exists a holomorphic map $\pi: X \rightarrow \mathbb{C}_{\infty}$ which satisfies $\pi \circ \phi=\pi$.

  comment

• Paper 4, Section I, J

  Statistical Modelling

  Part II, 2019

  In a normal linear model with design matrix $X \in \mathbb{R}^{n \times p}$, output variables $y \in \mathbb{R}^{n}$ and parameters $\beta \in \mathbb{R}^{p}$ and $\sigma^{2}>0$, define a $(1-\alpha)$-level prediction interval for a new observation with input variables $x^{*} \in \mathbb{R}^{p}$. Derive an explicit formula for the interval, proving that it satisfies the properties required by the definition. [You may assume that the maximum likelihood estimator $\hat{\beta}$ is independent of $\sigma^{-2}\|y-X \hat{\beta}\|_{2}^{2}$, which has a $\chi_{n-p}^{2}$ distribution.]

  comment

• Paper 3, Section I, J

  Statistical Modelling

  Part II, 2019

  (a) For a given model with likelihood $L(\beta), \beta \in \mathbb{R}^{p}$, define the Fisher information matrix in terms of the Hessian of the log-likelihood.

  Consider a generalised linear model with design matrix $X \in \mathbb{R}^{n \times p}$, output variables $y \in \mathbb{R}^{n}$, a bijective link function, mean parameters $\mu=\left(\mu_{1}, \ldots, \mu_{n}\right)$ and dispersion parameters $\sigma_{1}^{2}=\ldots=\sigma_{n}^{2}=\sigma^{2}$. Assume $\sigma^{2}$ is known.

  (b) State the form of the log-likelihood.

  (c) For the canonical link, show that when the parameter $\sigma^{2}$ is known, the Fisher information matrix is equal to

  $$\sigma^{-2} X^{T} W X$$

  for a diagonal matrix $W$ depending on the means $\mu$. Identify $W$.

  comment

• Paper 2, Section I, J

  Statistical Modelling

  Part II, 2019

  The cycling data frame contains the results of a study on the effects of cycling to work among 1,000 participants with asthma, a respiratory illness. Half of the participants, chosen uniformly at random, received a monetary incentive to cycle to work, and the other half did not. The variables in the data frame are:

  • miles: the average number of miles cycled per week

  • episodes: the number of asthma episodes experienced during the study

  • incentive: whether or not a monetary incentive to cycle was given

  • history: the number of asthma episodes in the year preceding the study

  Consider the $R$ code below and its abbreviated output.

  $>\operatorname{lm} .1=\operatorname{lm}$ (episodes miles $+$ history, data=cycling)

  $>\operatorname{summary}(1 \mathrm{~lm} .1)$

  Coefficients:

  Estimate Std. Error $t$ value $\operatorname{Pr}(>|t|)$

  (Intercept) $0.66937 \quad 0.07965 \quad 8.404<2 \mathrm{e}-16 * * *$

  miles $\quad-0.04917 \quad 0.01839-2.6740 .00761 * *$

  history $1.489540 .0481830 .918<2 \mathrm{e}-16 * * *$

  $>\operatorname{lm} .2=\operatorname{lm}($ episodes $~$ incentive $+$ history, data=cycling)

  $>$ summary (lm.2)

  Coefficients:

  Estimate Std. Error $t$ value $\operatorname{Pr}(>|t|)$

  (Intercept) $0.09539 \quad 0.06960 \quad 1.371 \quad 0.171$

  incentiveYes $0.91387 \quad 0.06504 \quad 14.051<2 \mathrm{e}-16 * * *$

  history $1.46806 \quad 0.04346 \quad 33.782<2 \mathrm{e}-16 * * *$

  $>\operatorname{lm} .3=\operatorname{lm}($ miles incentive $+$ history, data=cycling)

  $>\operatorname{summary}(\operatorname{lm} .3)$

  Coefficients :

  Estimate Std. Error t value $\operatorname{Pr}(>|t|)$

  (Intercept) $1.47050 \quad 0.11682 \quad 12.588<2 \mathrm{e}-16 * * *$

  incentiveYes $1.73282 \quad 0.10917 \quad 15.872<2 \mathrm{e}-16 * * *$

  history $\quad 0.47322 \quad 0.07294 \quad 6.487 \quad 1.37 \mathrm{e}-10 * * *$

  (a) For each of the fitted models, briefly explain what can be inferred about participants with similar histories.

  (b) Based on this analysis and the experimental design, is it advisable for a participant with asthma to cycle to work more often? Explain.

  comment

• Paper 1, Section I, J

  Statistical Modelling

  Part II, 2019

  The Gamma distribution with shape parameter $\alpha>0$ and scale parameter $\lambda>0$ has probability density function

  $$f(y ; \alpha, \lambda)=\frac{\lambda^{\alpha}}{\Gamma(\alpha)} y^{\alpha-1} e^{-\lambda y} \quad \text { for } y>0$$

  Give the definition of an exponential dispersion family and show that the set of Gamma distributions forms one such family. Find the cumulant generating function and derive the mean and variance of the Gamma distribution as a function of $\alpha$ and $\lambda$.

  comment

• Paper 4, Section II, J

  Statistical Modelling

  Part II, 2019

  A sociologist collects a dataset on friendships among $m$ Cambridge graduates. Let $y_{i, j}=1$ if persons $i$ and $j$ are friends 3 years after graduation, and $y_{i, j}=0$ otherwise. Let $z_{i}$ be a categorical variable for person $i$ 's college, taking values in the set $\{1,2, \ldots, C\}$. Consider logistic regression models,

  $$\mathbb{P}\left(y_{i, j}=1\right)=\frac{e^{\theta_{i, j}}}{1+e^{\theta_{i, j}}}, \quad 1 \leqslant i<j \leqslant m$$

  with parameters either

  1. $\theta_{i, j}=\beta_{z_{i}, z_{j}}$; or,

  2. $\theta_{i, j}=\beta_{z_{i}}+\beta_{z_{j}}$; or,

  3. $\theta_{i, j}=\beta_{z_{i}}+\beta_{z_{j}}+\beta_{0} \delta_{z_{i}, z_{j}}$, where $\delta_{z_{i}, z_{j}}=1$ if $z_{i}=z_{j}$ and 0 otherwise.

  (a) Write the likelihood of the models.

  (b) Show that the three models are nested and specify the order. Suggest a statistic to compare models 1 and 3, give its definition and specify its asymptotic distribution under the null hypothesis, citing any necessary theorems.

  (c) Suppose persons $i$ and $j$ are in the same college $k ;$ consider the number of friendships, $M_{i}$ and $M_{j}$, that each of them has with people in college $\ell \neq k$ ( $\ell$ and $k$ fixed). In each of the models above, compare the distribution of these two random variables. Explain why this might lead to a poor quality of fit.

  (d) Find a minimal sufficient statistic for model 3. [You may use the following characterisation of a minimal sufficient statistic: let $f(\beta ; y)$ be the likelihood in this model, where $\beta=\left(\beta_{k}\right)_{k=0,1, \ldots, C}$ and $y=\left(y_{i, j}\right)_{i, j=1, \ldots, m} ;$ suppose $T=t(y)$ is a statistic such that $f(\beta ; y) / f\left(\beta ; y^{\prime}\right)$ is constant in $\beta$ if and only if $t(y)=t\left(y^{\prime}\right)$; then, $T$ is a minimal sufficient statistic for $\beta$.]

  comment

• Paper 1, Section II, J

  Statistical Modelling

  Part II, 2019

  The ice_cream data frame contains the result of a blind tasting of 90 ice creams, each of which is rated as poor, good, or excellent. It also contains the price of each ice cream classified into three categories. Consider the $R$ code below and its output.

  

  (a) Write down the generalised linear model fitted by the code above.

  (b) Prove that the fitted values resulting from the maximum likelihood estimator of the coefficients in this model are identical to those resulting from the maximum likelihood estimator when fitting a Multinomial model which assumes the number of ice creams at each price level is fixed.

  (c) Using the output above, perform a goodness-of-fit test at the $1 \%$ level, specifying the null hypothesis, the test statistic, its asymptotic null distribution, any assumptions of the test and the decision from your test. (d) If we believe that better ice creams are more expensive, what could be a more powerful test against the model fitted above and why?

  comment

• Paper 4, Section II, D

  Statistical Physics

  Part II, 2019

  Give an outline of the Landau theory of phase transitions for a system with one real order parameter $\phi$. Describe the phase transitions that can be modelled by the Landau potentials (i) $G=\frac{1}{4} \phi^{4}+\frac{1}{2} \varepsilon \phi^{2}$, (ii) $G=\frac{1}{6} \phi^{6}+\frac{1}{4} g \phi^{4}+\frac{1}{2} \varepsilon \phi^{2}$,

  where $\varepsilon$ and $g$ are control parameters that depend on the temperature and pressure.

  In case (ii), find the curve of first-order phase transitions in the $(g, \varepsilon)$ plane. Find the region where it is possible for superheating to occur. Find also the region where it is possible for supercooling to occur.

  comment

• Paper 3, Section II, D

  Statistical Physics

  Part II, 2019

  What is meant by the chemical potential $\mu$ of a thermodynamic system? Derive the Gibbs distribution for a system at temperature $T$ and chemical potential $\mu$ (and fixed volume) with variable particle number $N$.

  Consider a non-interacting, two-dimensional gas of $N$ fermionic particles in a region of fixed area, at temperature $T$ and chemical potential $\mu$. Using the Gibbs distribution, find the mean occupation number $n_{F}(\varepsilon)$ of a one-particle quantum state of energy $\varepsilon$. Show that the density of states $g(\varepsilon)$ is independent of $\varepsilon$ and deduce that the mean number of particles between energies $\varepsilon$ and $\varepsilon+d \varepsilon$ is very well approximated for $T \ll \varepsilon_{F}$ by

  $$\frac{N}{\varepsilon_{F}} \frac{d \varepsilon}{e^{\left(\varepsilon-\varepsilon_{F}\right) / T+1}}$$

  where $\varepsilon_{F}$ is the Fermi energy. Show that, for $T$ small, the heat capacity of the gas has a power-law dependence on $T$, and find the power.

  comment

• Paper 2, Section II, D

  Statistical Physics

  Part II, 2019

  Using the classical statistical mechanics of a gas of molecules with negligible interactions, derive the $i$ deal gas law. Explain briefly to what extent this law is independent of the molecule's internal structure.

  Calculate the entropy $S$ of a monatomic gas of low density, with negligible interactions. Deduce the equation relating the pressure $P$ and volume $V$ of the gas on a curve in the $P V$-plane along which $S$ is constant.

  [You may use $\int_{-\infty}^{\infty} e^{-\alpha x^{2}} d x=\left(\frac{\pi}{\alpha}\right)^{\frac{1}{2}}$ for $\left.\alpha>0 .\right]$

  comment

• Paper 1, Section II, D

  Statistical Physics

  Part II, 2019

  (a) Explain, from a macroscopic and microscopic point of view, what is meant by an adiabatic change. A system has access to heat baths at temperatures $T_{1}$ and $T_{2}$, with $T_{2}>T_{1}$. Show that the most effective method for repeatedly converting heat to work, using this system, is by combining isothermal and adiabatic changes. Define the efficiency and calculate it in terms of $T_{1}$ and $T_{2}$.

  (b) A thermal system (of constant volume) undergoes a phase transition at temperature $T_{\mathrm{c}}$. The heat capacity of the system is measured to be

  $$C= \begin{cases}\alpha T & \text { for } T<T_{\mathrm{c}} \\ \beta & \text { for } T>T_{\mathrm{c}}\end{cases}$$

  where $\alpha, \beta$ are constants. A theoretical calculation of the entropy $S$ for $T>T_{\mathrm{c}}$ leads to

  $$S=\beta \log T+\gamma$$

  How can the value of the theoretically-obtained constant $\gamma$ be verified using macroscopically measurable quantities?

  comment

• Paper 4, Section II, K

  Stochastic Financial Models

  Part II, 2019

  (a) Describe the (Cox-Ross-Rubinstein) binomial model. What are the necessary and sufficient conditions on the model parameters for it to be arbitrage-free? How is the equivalent martingale measure $\mathbb{Q}$ characterised in this case?

  (b) Consider a discounted claim $H$ of the form $H=h\left(S_{0}^{1}, S_{1}^{1}, \ldots, S_{T}^{1}\right)$ for some function $h$. Show that the value process of $H$ is of the form

  $$V_{t}(\omega)=v_{t}\left(S_{0}^{1}, S_{1}^{1}(\omega), \ldots, S_{t}^{1}(\omega)\right)$$

  for $t \in\{0, \ldots, T\}$, where the function $v_{t}$ is given by

  $$v_{t}\left(x_{0}, \ldots, x_{t}\right)=\mathbb{E}_{\mathbb{Q}}\left[h\left(x_{0}, \ldots, x_{t}, x_{t} \cdot \frac{S_{1}^{1}}{S_{0}^{1}}, \ldots, x_{t} \cdot \frac{S_{T-t}^{1}}{S_{0}^{1}}\right)\right]$$

  You may use any property of conditional expectations without proof.

  (c) Suppose that $H=h\left(S_{T}^{1}\right)$ only depends on the terminal value $S_{T}^{1}$ of the stock price. Derive an explicit formula for the value of $H$ at time $t \in\{0, \ldots, T\}$.

  (d) Suppose that $H$ is of the form $H=h\left(S_{T}^{1}, M_{T}\right)$, where $M_{t}:=\max _{s \in\{0, \ldots, t\}} S_{s}^{1}$. Show that the value process of $H$ is of the form

  $$V_{t}(\omega)=v_{t}\left(S_{t}^{1}(\omega), M_{t}(\omega)\right)$$

  for $t \in\{0, \ldots, T\}$, where the function $v_{t}$ is given by

  $$v_{t}(x, m)=\mathbb{E}_{\mathbb{Q}}\left[g\left(x, m, S_{0}^{1}, S_{T-t}^{1}, M_{T-t}\right)\right]$$

  for a function $g$ to be determined.

  comment

• Paper 3, Section II, K

  Stochastic Financial Models

  Part II, 2019

  In the Black-Scholes model the price $\pi(C)$ at time 0 for a European option of the form $C=f\left(S_{T}\right)$ with maturity $T>0$ is given by

  $$\pi(C)=e^{-r T} \int_{-\infty}^{\infty} f\left(S_{0} \exp \left(\sigma \sqrt{T} y+\left(r-\frac{1}{2} \sigma^{2}\right) T\right)\right) \frac{1}{\sqrt{2 \pi}} e^{-y^{2} / 2} d y$$

  (a) Find the price at time 0 of a European call option with maturity $T>0$ and strike price $K>0$ in terms of the standard normal distribution function. Derive the put-call parity to find the price of the corresponding European put option.

  (b) The digital call option with maturity $T>0$ and strike price $K>0$ has payoff given by

  $$C_{\mathrm{digCall}}= \begin{cases}1 & \text { if } S_{T} \geqslant K \\ 0 & \text { otherwise }\end{cases}$$

  What is the value of the option at any time $t \in[0, T]$ ? Determine the number of units of the risky asset that are held in the hedging strategy at time $t$.

  (c) The digital put option with maturity $T>0$ and strike price $K>0$ has payoff

  $$C_{\text {digPut }}= \begin{cases}1 & \text { if } S_{T}<K \\ 0 & \text { otherwise. }\end{cases}$$

  Find the put-call parity for digital options and deduce the Black-Scholes price at time 0 for a digital put.

  comment

• Paper 2, Section II, $29 K$

  Stochastic Financial Models

  Part II, 2019

  (a) In the context of a multi-period model in discrete time, what does it mean to say that a probability measure is an equivalent martingale measure?

  (b) State the fundamental theorem of asset pricing.

  (c) Consider a single-period model with one risky asset $S^{1}$ having initial price $S_{0}^{1}=1$. At time 1 its value $S_{1}^{1}$ is a random variable on $(\Omega, \mathcal{F}, \mathbb{P})$ of the form

  $$S_{1}^{1}=\exp (\sigma Z+m), \quad m \in \mathbb{R}, \sigma>0,$$

  where $Z \sim \mathcal{N}(0,1)$. Assume that there is a riskless numéraire $S^{0}$ with $S_{0}^{0}=S_{1}^{0}=1$. Show that there is no arbitrage in this model.

  [Hint: You may find it useful to consider a density of the form $\exp (\tilde{\sigma} Z+\tilde{m})$ and find suitable $\tilde{m}$ and $\tilde{\sigma}$. You may use without proof that if $X$ is a normal random variable then $\mathbb{E}\left(e^{X}\right)=\exp \left(\mathbb{E}(X)+\frac{1}{2} \operatorname{Var}(X)\right)$.]

  (d) Now consider a multi-period model with one risky asset $S^{1}$ having a non-random initial price $S_{0}^{1}=1$ and a price process $\left(S_{t}^{1}\right)_{t \in\{0, \ldots, T\}}$ of the form

  $$S_{t}^{1}=\prod_{i=1}^{t} \exp \left(\sigma_{i} Z_{i}+m_{i}\right), \quad m_{i} \in \mathbb{R}, \sigma_{i}>0$$

  where $Z_{i}$ are i.i.d. $\mathcal{N}(0,1)$-distributed random variables on $(\Omega, \mathcal{F}, \mathbb{P})$. Assume that there is a constant riskless numéraire $S^{0}$ with $S_{t}^{0}=1$ for all $t \in\{0, \ldots, T\}$. Show that there exists no arbitrage in this model.

  comment

• Paper 1, Section II, 30K

  Stochastic Financial Models

  Part II, 2019

  (a) What does it mean to say that $\left(M_{n}, \mathcal{F}_{n}\right)_{n \geqslant 0}$ is a martingale? (b) Let $\left(X_{n}\right)_{n \geqslant 0}$ be a Markov chain defined by $X_{0}=0$ and

  $$\begin{aligned} & \mathbb{P}\left[X_{n}=0 \mid X_{n-1}=0\right]=1-\frac{1}{n} \end{aligned}$$

  $$\begin{aligned} &\mathbb{P}\left[X_{n}=1 \mid X_{n-1}=0\right]=\mathbb{P}\left[X_{n}=-1 \mid X_{n-1}=0\right]=\frac{1}{2 n} \\ &\mathbb{P}\left[X_{n}=0 \mid X_{n-1}=0\right]=1-\frac{1}{n} \end{aligned}$$

  and

  $$\mathbb{P}\left[X_{n}=n X_{n-1} \mid X_{n-1} \neq 0\right]=\frac{1}{n}, \quad \mathbb{P}\left[X_{n}=0 \mid X_{n-1} \neq 0\right]=1-\frac{1}{n}$$

  for $n \geqslant 1$. Show that $\left(X_{n}\right)_{n \geqslant 0}$ is a martingale with respect to the filtration $\left(\mathcal{F}_{n}\right)_{n} \geqslant 0$ where $\mathcal{F}_{0}$ is trivial and $\mathcal{F}_{n}=\sigma\left(X_{1}, \ldots, X_{n}\right)$ for $n \geqslant 1$.

  (c) Let $M=\left(M_{n}\right)_{n \geqslant 0}$ be adapted with respect to a filtration $\left(\mathcal{F}_{n}\right)_{n \geqslant 0}$ with $\mathbb{E}\left[\left|M_{n}\right|\right]<\infty$ for all $n$. Show that the following are equivalent:

  (i) $M$ is a martingale.

  (ii) For every stopping time $\tau$, the stopped process $M^{\tau}$ defined by $M_{n}^{\tau}:=M_{n \wedge \tau}$, $n \geqslant 0$, is a martingale.

  (iii) $\mathbb{E}\left[M_{n \wedge \tau}\right]=\mathbb{E}\left[M_{0}\right]$ for all $n \geqslant 0$ and every stopping time $\tau$.

  [Hint: To show that (iii) implies (i) you might find it useful to consider the stopping time

  $$T(\omega):= \begin{cases}n & \text { if } \omega \in A, \\ n+1 & \text { if } \omega \notin A,\end{cases}$$

  for any $\left.A \in \mathcal{F}_{n .} .\right]$

  comment

• Paper 4, Section I, H

  Topics in Analysis

  Part II, 2019

  Show that $\pi$ is irrational. [Hint: consider the functions $f_{n}:[0, \pi] \rightarrow \mathbb{R}$ given by $\left.f_{n}(x)=x^{n}(\pi-x)^{n} \sin x .\right]$

  comment

• Paper 3, Section I, H

  Topics in Analysis

  Part II, 2019

  State Nash's theorem for a non zero-sum game in the case of two players with two choices.

  The role playing game Tixerb involves two players. Before the game begins, each player $i$ chooses a $p_{i}$ with $0 \leqslant p_{i} \leqslant 1$ which they announce. They may change their choice as many times as they wish, but, once the game begins, no further changes are allowed. When the game starts, player $i$ becomes a Dark Lord with probability $p_{i}$ and a harmless peasant with probability $1-p_{i}$. If one player is a Dark Lord and the other a peasant the Lord gets 2 points and the peasant $-2$. If both are peasants they get 1 point each, if both Lords they get $-U$ each. Show that there exists a $U_{0}$, to be found, such that, if $U>U_{0}$ there will be three choices of $\left(p_{1}, p_{2}\right)$ for which neither player can increase the expected value of their outcome by changing their choice unilaterally, but, if $U_{0}>U$, there will only be one. Find the appropriate $\left(p_{1}, p_{2}\right)$ in each case.

  comment

• Paper 2, Section I, H

  Topics in Analysis

  Part II, 2019

  Let $\mathcal{K}$ be the collection of non-empty closed bounded subsets of $\mathbb{R}^{n}$.

  (a) Show that, if $A, B \in \mathcal{K}$ and we write

  $$A+B=\{a+b: a \in A, b \in B\}$$

  then $A+B \in \mathcal{K}$.

  (b) Show that, if $K_{n} \in \mathcal{K}$, and

  $$K_{1} \supseteq K_{2} \supseteq K_{3} \supseteq \cdots$$

  then $K:=\bigcap_{n=1}^{\infty} K_{n} \in \mathcal{K}$.

  (c) Assuming the result that

  $$\rho(A, B)=\sup _{a \in A} \inf _{b \in B}|a-b|+\sup _{b \in B} \inf _{a \in A}|a-b|$$

  defines a metric on $\mathcal{K}$ (the Hausdorff metric), show that if $K_{n}$ and $K$ are as in part (b), then $\rho\left(K_{n}, K\right) \rightarrow 0$ as $n \rightarrow \infty$.

  comment

• Paper 1, Section I, H

  Topics in Analysis

  Part II, 2019

  Let $T_{n}$ be the $n$th Chebychev polynomial. Suppose that $\gamma_{i}>0$ for all $i$ and that $\sum_{i=1}^{\infty} \gamma_{i}$ converges. Explain why $f=\sum_{i=1}^{\infty} \gamma_{i} T_{3^{i}}$ is a well defined continuous function on $[-1,1]$.

  Show that, if we take $P_{n}=\sum_{i=1}^{n} \gamma_{i} T_{3^{i}}$, we can find points $x_{k}$ with

  $$-1 \leqslant x_{0}<x_{1}<\ldots<x_{3^{n+1}} \leqslant 1$$

  such that $f\left(x_{k}\right)-P_{n}\left(x_{k}\right)=(-1)^{k+1} \sum_{i=n+1}^{\infty} \gamma_{i}$ for each $k=0,1, \ldots, 3^{n+1}$.

  Suppose that $\delta_{n}$ is a decreasing sequence of positive numbers and that $\delta_{n} \rightarrow 0$ as $n \rightarrow \infty$. Stating clearly any theorem that you use, show that there exists a continuous function $f$ with

  $$\sup _{t \in[-1,1]}|f(t)-P(t)| \geqslant \delta_{n}$$

  for all polynomials $P$ of degree at most $n$ and all $n \geqslant 1$.

  comment

• Paper 2, Section II, H

  Topics in Analysis

  Part II, 2019

  Throughout this question $I$ denotes the closed interval $[-1,1]$.

  (a) For $n \in \mathbb{N}$, consider the $2 n+1$ points $r / n \in I$ with $r \in \mathbb{Z}$ and $-n \leqslant r \leqslant n$. Show that, if we colour them red or green in such a way that $-1$ and 1 are coloured differently, there must be two neighbouring points of different colours.

  (b) Deduce from part (a) that, if $I=A \cup B$ with $A$ and $B$ closed, $-1 \in A$ and $1 \in B$, then $A \cap B \neq \emptyset$.

  (c) Deduce from part (b) that there does not exist a continuous function $f: I \rightarrow \mathbb{R}$ with $f(t) \in\{-1,1\}$ for all $t \in I$ and $f(-1)=-1, f(1)=1$.

  (d) Deduce from part (c) that if $f: I \rightarrow I$ is continuous then there exists an $x \in I$ with $f(x)=x$.

  (e) Deduce the conclusion of part (c) from the conclusion of part (d).

  (f) Deduce the conclusion of part (b) from the conclusion of part (c).

  (g) Suppose that we replace $I$ wherever it occurs by the unit circle

  $$C=\{z \in \mathbb{C}|| z \mid=1\}$$

  Which of the conclusions of parts (b), (c) and (d) remain true? Give reasons.

  comment

• Paper 4, Section II, H

  Topics in Analysis

  Part II, 2019

  (a) Suppose that $K \subset \mathbb{C}$ is a non-empty subset of the square $\{x+i y: x, y \in(-1,1)\}$ and $f$ is analytic in the larger square $\{x+i y: x, y \in(-1-\delta, 1+\delta)\}$ for some $\delta>0$. Show that $f$ can be uniformly approximated on $K$ by polynomials.

  (b) Let $K$ be a closed non-empty proper subset of $\mathbb{C}$. Let $\Lambda$ be the set of $\lambda \in \mathbb{C} \backslash K$ such that $g_{\lambda}(z)=(z-\lambda)^{-1}$ can be approximated uniformly on $K$ by polynomials and let $\Gamma=\mathbb{C} \backslash(K \cup \Lambda)$. Show that $\Lambda$ and $\Gamma$ are open. Is it always true that $\Lambda$ is non-empty? Is it always true that, if $K$ is bounded, then $\Gamma$ is empty? Give reasons.

  [No form of Runge's theorem may be used without proof.]

  comment

• Paper 4, Section II, A

  Waves

  Part II, 2019

  (a) Assuming a slowly-varying two-dimensional wave pattern of the form

  $$\varphi(\mathbf{x}, t)=A(\mathbf{x}, t ; \varepsilon) \exp \left[\frac{i}{\varepsilon} \theta(\mathbf{x}, t)\right]$$

  where $0<\varepsilon \ll 1$, and a local dispersion relation $\omega=\Omega(\mathbf{k} ; \mathbf{x}, t)$, derive the ray tracing equations,

  $$\frac{d x_{i}}{d t}=\frac{\partial \Omega}{\partial k_{i}}, \quad \frac{d \omega}{d t}=\frac{\partial \Omega}{\partial t}, \quad \frac{d k_{i}}{d t}=-\frac{\partial \Omega}{\partial x_{i}}, \quad \frac{1}{\varepsilon} \frac{d \theta}{d t}=-\omega+k_{j} \frac{\partial \Omega}{\partial k_{j}}$$

  for $i, j=1,2$, explaining carefully the meaning of the notation used.

  (b) For a homogeneous, time-independent (but not necessarily isotropic) medium, show that all rays are straight lines. When the waves have zero frequency, deduce that if the point $\mathbf{x}$ lies on a ray emanating from the origin in the direction given by a unit vector $\widehat{\mathbf{c}}_{\mathrm{g}}$, then

  $$\theta(\mathbf{x})=\theta(\mathbf{0})+\widehat{\mathbf{c}}_{\mathbf{g}} \cdot \mathbf{k}|\mathbf{x}|$$

  (c) Consider a stationary obstacle in a steadily moving homogeneous medium which has the dispersion relation

  $$\Omega=\alpha\left(k_{1}^{2}+k_{2}^{2}\right)^{1 / 4}-V k_{1}$$

  where $(V, 0)$ is the velocity of the medium and $\alpha>0$ is a constant. The obstacle generates a steady wave system. Writing $\left(k_{1}, k_{2}\right)=\kappa(\cos \phi, \sin \phi)$, with $\kappa>0$, show that the wave satisfies

  $$\kappa=\frac{\alpha^{2}}{V^{2} \cos ^{2} \phi}, \quad \widehat{\mathbf{c}}_{\mathrm{g}}=(\cos \psi, \sin \psi)$$

  where $\psi$ is defined by

  $$\tan \psi=-\frac{\tan \phi}{1+2 \tan ^{2} \phi}$$

  with $\frac{1}{2} \pi<\psi<\frac{3}{2} \pi$ and $-\frac{1}{2} \pi<\phi<\frac{1}{2} \pi$. Deduce that the wave pattern occupies a wedge of semi-angle $\tan ^{-1}\left(2^{-3 / 2}\right)$, extending in the negative $x_{1}$-direction.

  comment

• Paper 2, Section II, A

  Waves

  Part II, 2019

  The linearised equation of motion governing small disturbances in a homogeneous elastic medium of density $\rho$ is

  $$\rho \frac{\partial^{2} \mathbf{u}}{\partial t^{2}}=(\lambda+\mu) \nabla(\boldsymbol{\nabla} \cdot \mathbf{u})+\mu \nabla^{2} \mathbf{u}$$

  where $\mathbf{u}(\mathbf{x}, t)$ is the displacement, and $\lambda$ and $\mu$ are the Lamé moduli.

  (a) The medium occupies the region between a rigid plane boundary at $y=0$ and a free surface at $y=h$. Show that $S H$ waves can propagate in the $x$-direction within this region, and find the dispersion relation for such waves.

  (b) For each mode, deduce the cutoff frequency, the phase velocity and the group velocity. Plot the latter two velocities as a function of wavenumber.

  (c) Verify that in an average sense (to be made precise), the wave energy flux is equal to the wave energy density multiplied by the group velocity.

  [You may assume that the elastic energy per unit volume is given by

  $$\left.E_{p}=\frac{1}{2} \lambda e_{i i} e_{j j}+\mu e_{i j} e_{i j} \cdot\right]$$

  comment

• Paper 3, Section II, A

  Waves

  Part II, 2019

  (a) Derive the wave equation for perturbation pressure for linearised sound waves in a compressible gas.

  (b) For a single plane wave show that the perturbation pressure and the velocity are linearly proportional and find the constant of proportionality, i.e. the acoustic impedance.

  (c) Gas occupies a tube lying parallel to the $x$-axis. In the regions $x<0$ and $x>L$ the gas has uniform density $\rho_{0}$ and sound speed $c_{0}$. For $0<x<L$ the temperature of the gas has been adjusted so that it has uniform density $\rho_{1}$ and sound speed $c_{1}$. A harmonic plane wave with frequency $\omega$ and unit amplitude is incident from $x=-\infty$. If $T$ is the (in general complex) amplitude of the wave transmitted into $x>L$, show that

  $$|T|=\left(\cos ^{2} k_{1} L+\frac{1}{4}\left(\lambda+\lambda^{-1}\right)^{2} \sin ^{2} k_{1} L\right)^{-\frac{1}{2}}$$

  where $\lambda=\rho_{1} c_{1} / \rho_{0} c_{0}$ and $k_{1}=\omega / c_{1}$. Discuss both of the limits $\lambda \ll 1$ and $\lambda \gg 1$.

  comment

• Paper 1, Section II, A

  Waves

  Part II, 2019

  The equation of state relating pressure $p$ to density $\rho$ for a perfect gas is given by

  $$\frac{p}{p_{0}}=\left(\frac{\rho}{\rho_{0}}\right)^{\gamma}$$

  where $p_{0}$ and $\rho_{0}$ are constants, and $\gamma>1$ is the specific heat ratio.

  (a) Starting from the equations for one-dimensional unsteady flow of a perfect gas of uniform entropy, show that the Riemann invariants,

  $$R_{\pm}=u \pm \frac{2}{\gamma-1}\left(c-c_{0}\right)$$

  are constant on characteristics $C_{\pm}$given by

  $$\frac{d x}{d t}=u \pm c$$

  where $u(x, t)$ is the velocity of the gas, $c(x, t)$ is the local speed of sound, and $c_{0}$ is a constant.

  (b) Such an ideal gas initially occupies the region $x>0$ to the right of a piston in an infinitely long tube. The gas and the piston are initially at rest. At time $t=0$ the piston starts moving to the left with path given by

  $$x=X_{p}(t), \quad \text { with } X_{p}(0)=0 .$$

  (i) Solve for $u(x, t)$ and $\rho(x, t)$ in the region $x>X_{p}(t)$ under the assumptions that $-\frac{2 c_{0}}{\gamma-1}<\dot{X}_{p}<0$ and that $\left|\dot{X}_{p}\right|$ is monotonically increasing, where dot indicates a time derivative.

  [It is sufficient to leave the solution in implicit form, i.e. for given $x, t$ you should not attempt to solve the $C_{+}$characteristic equation explicitly.]

  (ii) Briefly outline the behaviour of $u$ and $\rho$ for times $t>t_{c}$, where $t_{c}$ is the solution to $\dot{X}_{p}\left(t_{c}\right)=-\frac{2 c_{0}}{\gamma-1}$.

  (iii) Now suppose,

  $$X_{p}(t)=-\frac{t^{1+\alpha}}{1+\alpha}$$

  where $\alpha \geqslant 0$. For $0<\alpha \ll 1$, find a leading-order approximation to the solution of the $C_{+}$characteristic equation when $x=c_{0} t-a t, 0<a<\frac{1}{2}(\gamma+1)$ and $t=O(1)$.

  [Hint: You may find it useful to consider the structure of the characteristics in the limiting case when $\alpha=0$.]

  comment